Wednesday, August 10, 2016

1000 Coins and 10 Bags - Algorithm and Solution in Java

Posted by Sharath Chandra
Dear Friends, 

Recently I have came across this below question and I solved and wanted to try this in Java Programmatic way. Please leave your comments if you have a better solution. 

Question: 

You have 1000 coins and you have to arrange these coins in 10 Bags. On request for any number given from 1-1000 you should tell which and all bags user should take. 


Think about answer; 


|
|
|
|
|


|
|
|
|
|


|
|
|
|
|


|
|
|
|
|



|
|
|
|
|


|
|
|
|
|



|
|
|
|
|



|
|
|
|
|


|
|
|
|
|



Solution: 

You should arrange them according to Binary format. i.e. 

1st Bag - 2power0 - i.e. 1 

2nd Bag - 2power1 - i.e. 2

3rd Bag - 2power2 - i.e. 4 

4th Bag - 2power3 - i.e.

5th Bag - 2power4 - i.e. 16 

6th Bag - 2power5 - i.e. 32 

7th Bag - 2power6 - i.e. 64 

8th Bag- 2power7 - i.e. 128 

9th Bag - 2power8 - i.e. 256 

10th Bag - Remaining - i.e. (1+2+4+8+16+32+64+128+256)-1000 = 489 


So given - 345 then user can be given with 

From Bag no 9 i.e. the value of this bucket 256
From Bag no 7 i.e. the value of this bucket 64
From Bag no 5 i.e. the value of this bucket 16
From Bag no 4 i.e. the value of this bucket 8

From Bag no 1 i.e. the value of this bucket 1



For this I have written the program - where user needs to enter the given value 1-1000 and it will display the best solution. (above 512 it will take the other way of counting.) 

You can see the solution in this link 




Please share this with your friends - because in Knowledge 
SHARING IS GAINING