Monday 12 November 2012

Shopkeeper Problem with Solution

  Adjust the font size     Reset ↕

Problem 1: One Side Only (Simple)

This 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, 512.


Problem 2: Both Sides (Medium)
For this answer is 3^0,3^1,3^2 …. That is 1,3,9,27,81,243,729


Problem 3: Incremental (Hard)
This is exactly a problem solved by Gray code.
Gray codes are named after the Frank Gray who patented their use for shaft encoders in 1953
A Gray code represents each number in the sequence of integers {0...2^N-1} as a binary string of length N in an order such that adjacent integers have Gray code representations that differ in only one bit position. Marching through the integer sequence therefore requires flipping just one bit at a time.

Example (N=3): The binary coding of {0...7} is {000, 001, 010, 011,
100, 101, 110, 111}, while one Gray coding is {000, 001, 011, 010,
110, 111, 101, 100}.

For this answer we need as many blocks as per Solution to Problem 1.
For easy understanding let me describe the case where the packets range from 1 to 7 which can be easily extended to 1 - 125 range.
Now if we want to make packets of all weights from 1 to & we will do the following

001 We measure 1kg,using 1kg block.
011 We measure 3kg by placing 2 kg block also
010 We remove 1kg block and measure 2 kg.
110 We add 4kg weight and measure 6kg weight …
………….

Now we can see answer to our problem is Gray code of 7 bits. Now our range is 1 to 125 and not 1 to 127.This can be solved by using appropriate Gray code making the following numbers falling to the end of the sequence you are starting with
1111 110
1111 111


POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Click Here To add Comment

Your feedback is always appreciated.
I will try to reply to your queries as soon as time allows.
Please do not spam Spam comments will be deleted immediately upon our review.

Blogger Widgets

Recent comments

Send Quick Massage

Name

Email *

Message *

Recent posts

Total Pageviews

Blog Archive