**Simple Simple Google Interview Puzzle - 7 September**

The puzzle is if the shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1, 3 and 4 only. Now the question is how many minimum weights and names the weights you will need to measure all weights from 1 to 1000.

**For Solution :**Click Here

Total 12 weight of 1, 2, 2, 5, 10, 10, 20, 50, 100, 200, 200, 500.

ReplyDeleteminimum weight required: 2 (weight 1 and weight 3 only)

ReplyDelete1, 2, 4, 8, 16, 32, 64, 128, 256, 512. Takes ten.

ReplyDeleteCeiling(log2(1000)) = 10

ReplyDeleteThis problem can be seen more abstractly as trying to encode any integer between 1 and 1000 in the fewest bits possible. (Integers corresponding to the integer weights, and bits corresponding to unique weights).

As such, you need at least the lowest integer greater than the base 2 log of the number of unique weights, which is ten. Constructing an example shows that 10 is also the upper bound. (i.e. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512)

Has any one considered that you can add weights on the opposite side as well?

ReplyDeletethats puzzle coming soon

ReplyDeletei understand the solution but an anyone explain to me why we took 2 as a base ....plz

ReplyDeletewhat is d solution??

ReplyDeleteThere is a link after every puzzle

ReplyDeleteFor Solution : Click Here.

click on that link to get soln

You can think of it this way in if you take the 1,2,4,8,16 numbering system then each time you are only choosing a new number only when all other combination of the already present number is exhausted.

ReplyDeleteexample:-

after 1, 2

3 is not chosen.4 is only chosen because both all combination of the possible numbers is done.

similary 8 is chosen only when all other combination of three numbers(1,2,4) is done(which is 3c0+3c1+3c2+3c3 = 8(0-7)).

So by induction we can prove that this is the best way

1,3,9,27,81,243,729 only seven wt want

ReplyDeleteusing these 7 weights we cant measure 2,5,6,7 and so on... therefore taking base as two is the right approach!

ReplyDeleteThis is simply the numbers 2^0,2^1,2^2 ... that is 1,2,4,8,16... So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, and 512

ReplyDeleteThe answer for the number of ights is : 7

ReplyDeletebut the anser of weights is not unique:

1, 3, 9, 27, 81, 243, 636

1, 3, 9, 27, 81, 243, 637

1, 3, 9, 27, 81, 243, 638

1, 3, 9, 27, 81, 243, 639

................

................

1, 3, 9, 27, 81, 243, 729

and even more

Deleteguys provided answer is looks wrong

ReplyDeletefor ex: 1, 2, 4, 8, 16, 32, 64, 128, and 512 with this numbers

you can't count: 27 (by placing one sided only)

i guess correct ans: arithmetic progression from 1 to 45

off course 1+2+8+16

Delete