Interview Question
Country: United States
Look at first 5 coins (5ruppes,1rupees,50paisa,25paisa,10paisa): none of them can be formed by sum of any subset of others 7 coins. Easy to check that since coin[i] > coin[i+1] + coin[i+2], for i = 1..5
Thus, using first 5 coins we can form 2^5 -1 none zero sums.
For last 3 coins (3paisa,2paisa and 1paisa): we can form only 6 different none zero sums, that is, 1, 2, 3, 4, 5, and 6.
So, the total number of sums can be formed is 6 * (2^5-1) + 6 + (2^5-1) + 1 (for zero-sum).
Please tell me if I am wrong! Thanks!
We have 2 choices for choosing a coin or not choosing it: 2^8
- mahdi.oraei February 26, 2014The situation that (3paisa is chosen and 1paisa and 2 paisa is not chosen) or (3paisa is not chosen and 1 paisa and 2 paisa is chosen) is counted twice: each situation: 2^5 ( since 1paisa, 2paisa, and 3 paisa does not have the choice. they are already set!)
2^8 - 2^5 is the answer!