## Amazon Interview Question

SDE-3s**Country:**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