Shopkeeper Problem with Solution

Tweet

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

  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