Interview Question
Country: United States
or mathematical induction
if 1,2,4,...,2^k can form any number between 0 and 2^(k+1)-1
then 1,2,4,...,2^k,2^(k+1) can form:
- any number between 0 and 2^(k+1)-1 (if we dont make use of the last term), and
- any number between 2^(k+1)+0 and 2^(k+1)+ 2^(k+1)-1 (if we make use of the last term)
therefore it can form any number between 0 and 2^(k+1)+ 2^(k+1)-1 = 2^(k+2)-1.
by MI, this stmt is true: 1,2,4,...,2^n can form any number between 0 and 2^(n+1)-1
now we know 1 2 4 ... 32 can form number between 0 and 63. for number between 64 and 100, we can make use of 37, the remainder would be between 27 and 63 which then can be formed by 1 2 4 ... 32
I didn't get the idea for the numbers between 64-100. Can anyone explain it more clearly.
Thanks in advance :)
for any n between 64 and 100. we will first pick 37 to "make" n. Then the remaining number,r = n-37, is between 64 - 37 (27) and 100-37 (63). Since r is between 0 and 63, it can be made using 1,2,4,8,...32
Can you tell me why you are picking 37 first why not any other number ???
Please Explain it.
Thanks
look my friend the scenario bfor 37,if u add all of them u get a sum of 63.. u need 37 more to get 100,else it will cross 100.
hence we chose 37..
Think binary !
- learner May 16, 2012