back to blog index

You have a table called Vouchers

You have a table called Vouchers where you store information about
vouchers, including voucher id (vid) and amount (amt). Run the following
code to create the Vouchers table and populate it with sample data:

SET NOCOUNT ON;
USE tempdb;
GO
IF OBJECT_ID('dbo.Vouchers') IS NOT NULL DROP TABLE dbo.Vouchers;
GO

CREATE TABLE dbo.Vouchers
(
  vid INT NOT NULL PRIMARY KEY,
  amt MONEY NOT NULL
);
GO

INSERT INTO dbo.Vouchers(vid, amt) VALUES(1, 500.0);
INSERT INTO dbo.Vouchers(vid, amt) VALUES(2, 100.0);
INSERT INTO dbo.Vouchers(vid, amt) VALUES(3, 30.0);
INSERT INTO dbo.Vouchers(vid, amt) VALUES(4, 90.0);
INSERT INTO dbo.Vouchers(vid, amt) VALUES(5, 40.0);
INSERT INTO dbo.Vouchers(vid, amt) VALUES(6, 90.0);
GO
Your task is to write a solution that returns all distinct sums of amounts that
can be produced by combining vouchers (one or more). The desired result
for the given sample data is (43 rows):
amt
---------------------
30.00
40.00
70.00
90.00
100.00
120.00
130.00
140.00
160.00
170.00
180.00
190.00
210.00
220.00
230.00
250.00
260.00
280.00
310.00
320.00
350.00
500.00
530.00
540.00
570.00
590.00
600.00
620.00
630.00
640.00
660.00
670.00
680.00
690.00
710.00
720.00
730.00
750.00
760.00
780.00
810.00
820.00
850.00
Cheers,
--
BG

End of Article



You must log on before posting a comment.

If you don't have a username & password, please register now.

Reader Comments

-- Here's a shot. Probably not terrible efficient, though.

with VouchersNumbered(k,amt) as ( select row_number() over ( order by vid ), amt from dbo.Vouchers ), Two(i) as ( select 0 union all select 1 ), Sums(lastUsed,amt) as ( select cast(1 as bigint), cast(i*amt as money) from VouchersNumbered cross join Two where k = 1 union all select VouchersNumbered.k, Sums.amt + i*VouchersNumbered.amt from VouchersNumbered, Sums, Two where VouchersNumbered.k = Sums.lastUsed + 1 ) select distinct amt from Sums where amt > $0 order by amt;

go

stevekass

Article Rating 5 out of 5

-- This should do better for larger tables with duplicates.

with VouchersNumbered(k,ct,amt) as ( select distinct dense_rank() over ( order by amt ), count(vid) over ( partition by amt ), max(amt) over ( partition by amt ) from dbo.Vouchers ), Nums(n) as ( select 0 union all select distinct ct from VouchersNumbered ), Sums(lastUsed,amt) as ( select cast(1 as bigint), cast(n*amt as money) from VouchersNumbered cross apply ( select n from Nums where Nums.n <= VouchersNumbered.ct ) as Vn where k = 1 union all select VouchersNumbered.k, Sums.amt + n*VouchersNumbered.amt from VouchersNumbered cross apply ( select n from Nums where Nums.n <= VouchersNumbered.ct ) as Vn cross join Sums where VouchersNumbered.k = Sums.lastUsed + 1 ) select distinct amt from Sums where amt > $0 order by amt;

stevekass

Article Rating 5 out of 5

How's this? I'm using bitwise operators to see if we've already used the voucher. If you want to see the combination that makes each value, just include the 'bits' column in the output (which gives 63 rows instead of 43).

with v as ( select *, power(2,vid-1) as bits from dbo.Vouchers ), all_v as ( select amt, bits from v

union all

select a.amt + v.amt, a.bits + v.bits from all_v a join v on a.bits & v.bits = 0 ) select distinct amt from all_v order by amt;

Rob http://msmvps.com/blogs/robfarley

rob_farley

Article Rating 5 out of 5

/* This fixes an error in my second solution. The derived table I used for Nums was incorrect, and could have gaps in it (though it did not for the example given here.) */

with VouchersCounted(k,ct,amt,r) as ( select dense_rank() over ( order by amt ), count(vid) over ( partition by amt ), max(amt) over ( partition by amt ), row_number() over ( partition by amt order by vid ) from dbo.Vouchers ), VouchersNumbered(k,ct,amt) as ( select k, ct, amt from VouchersCounted where r = 1 ), Nums(n) as ( select 0 union all select distinct r from VouchersCounted ), Sums(lastUsed,amt) as ( select cast(1 as bigint), cast(n*amt as money) from VouchersNumbered cross apply ( select n from Nums where Nums.n <= VouchersNumbered.ct ) as Vn where k = 1 union all select VouchersNumbered.k, Sums.amt + n*VouchersNumbered.amt from VouchersNumbered cross apply ( select n from Nums where Nums.n <= VouchersNumbered.ct ) as Vn cross join Sums where VouchersNumbered.k = Sums.lastUsed + 1 ) select distinct amt from Sums where amt > $0 order by amt;

stevekass

Article Rating 5 out of 5

/* Ok, here's a multi-statement solution that is fast when there are many vouchers. */

declare @Nums table ( n int primary key );

with Nums(r) as ( select row_number() over ( partition by amt order by vid ) from dbo.Vouchers ) insert into @Nums select 0 union all select distinct r from Nums;

declare @VouchersNumbered table ( k int primary key, ct int, amt money ); with VouchersCounted(k,ct,amt,r) as ( select dense_rank() over ( order by amt ), count(vid) over ( partition by amt ), max(amt) over ( partition by amt ), row_number() over ( partition by amt order by vid ) from dbo.Vouchers ), VouchersNumbered(k,ct,amt) as ( select k, ct, amt from VouchersCounted where r = 1 ), Nums(n) as ( select 0 union all select distinct r from VouchersCounted ) insert into @VouchersNumbered select k, ct, amt from VouchersNumbered;

declare @last int; set @last = ( select max(k) from @VouchersNumbered );

declare @lastUsed int; set @lastUsed = 1;

declare @Sums table ( lastUsed int, amt money, primary key(lastUsed, amt) );

insert into @Sums select @last, cast(n*amt as money) from @VouchersNumbered as V join @Nums as N on N.n <= V.ct where V.k = 1; set @lastUsed = 1; while @lastUsed < @last begin insert into @Sums select distinct @lastUsed + 1, S.amt + N.n*V.amt from @VouchersNumbered as V join @Nums as N on N.n between 1 and V.ct cross join @Sums as S where V.k = @lastUsed + 1 and S.amt + N.n*V.amt not in ( select amt from @Sums ) set @lastUsed = @lastUsed + 1; end;

select distinct amt from @Sums where amt > $0 order by amt;

stevekass

Article Rating 5 out of 5

I like that puzzle, you just have to know how recursive queries work :-)

WITH cte (vid, amt) AS ( SELECT vid, amt FROM vouchers UNION ALL SELECT v.vid, cte.amt + v.amt FROM vouchers AS v JOIN cte ON v.vid < cte.vid ) SELECT DISTINCT amt FROM cte

Hopefully there's no syntax error, because i only tested it on my Teradata system.

dnoeth

Article Rating 5 out of 5

Here's another one that copes with larger data sets. It even uses a cursor! (boo, hiss... but it performs more than adequately, so I don't mind)

create table #v (amt money); insert #v values (0); declare @amt money; declare csr cursor fast_forward for select amt from dbo.Vouchers; open csr; fetch csr into @amt; while (@@fetch_status = 0) begin insert #v select distinct amt + @amt from #v v1 where not exists (select * from #v v2 where v2.amt = v1.amt + @amt); fetch csr into @amt; end close csr; deallocate csr; select * from #v; drop table #v;

Rob

rob_farley

Article Rating 5 out of 5

Hi Rob, this scales much better than my CTE :-)

But if you modify the cursor to "select amt from dbo.Vouchers order by amt" it's even faster, because the probability to calculate an existing sum is higher.

Dieter

dnoeth

Article Rating 5 out of 5

 

   1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31   
or

More blogs about technology,
databases, and SQL Server.