-->

# 1000 Coins and 10 Bags - Algorithm and Solution in Java

Posted by Sharath
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.

|
|
|
|
|

|
|
|
|
|

|
|
|
|
|

|
|
|
|
|

|
|
|
|
|

|
|
|
|
|

|
|
|
|
|

|
|
|
|
|

|
|
|
|
|

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