Amazon Interview Question
SDE-3sCountry: United States
Let's define / as integer division and % as modulo or remainder
For N <34, most of the numbers do not have a valid solution except where N%3=0 or (N-17)%3 =0, these cases are trivial.
For N>=34, calculate NUM17=N / 17 and P=N%17
Fetch D1,D2,D3 using the following table
P D17 D6 D3
0 0 0 0
1 -1 3 0
2 -2 6 0
3 0 0 1
4 -1 3 1
5 -2 6 1
6 0 1 0
7 -1 4 0
8 -2 7 0
9 0 1 1
10 -1 4 1
11 -2 7 1
12 0 2 0
13 -1 5 0
14 -2 8 0
15 0 2 1
16 -1 5 1
The number of coins we need is:
Denomination 17 = NUM17+D17
Denomination 6 = D6
Denomination 3 = D3
For N<34 there is only a solution if N%3==0 or (N-17)%3=0.
For N>=34, P=N%17. P is a value between 0..16, use it as index and get D17,D6,D3 from this table:
P D17 D6 D3
0 0 0 0
1 -1 3 0
2 -2 6 0
3 0 0 1
4 -1 3 1
5 -2 6 1
6 0 1 0
7 -1 4 0
8 -2 7 0
9 0 1 1
10 -1 4 1
11 -2 7 1
12 0 2 0
13 -1 5 0
14 -2 8 0
15 0 2 1
16 -1 5 1
Coins 17 = TRUNC(N / 17) + D17
Coins 6 = D6
Coins 3 = D3
dude where are you getting all these questions from, I doubt they are all from amazon
- Anonymous May 05, 2019