Interview Questions And Answers 
-
“You have b boxes and n dollars. If I want any amount of money from 0 to n dollars, you must be able to hand me 0 to b boxes so that I get exactly what I request.” The two questions were “What are the restrictions on b and n, and how is money distributed among the boxes?”
6,081 Views |
(12 votes, avg: 4)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Screw the restriction crap, just have all the boxes aligned. Then for the first box
put in $1. The second box, $2. The third box $4. Notice the binary increments, that is the trick here, think in terms of bits.
box 1 = $1
box 2 = $2
box 3 = $4
box 4 = $8
.
.
box 8 = $(2^7)
.
.
etc
I think the only thing youre missing what do you do when you have some money left over? For example, if you have $14 and
Box 1 has $1
Box 2 has $2
Box 3 has $4
Box 4 has $8
Then you have $7 left over.
so you need to put whatevers left over in the last box?
What is the relation between b and n?
Is it [log n to base 2] + 2=b
where [] denote integral part of the log base 2 of n …?
sorry..if its incorrect:)
The trick is of Binary Numbers
2^0=1
2^1=2
2^2=4
2^3=8
2^4=16
….
…
2^7=128
…
..
The formula is [log n to base 2] + 1 = b
where [] denote integral part of the log base 2 of n
Example
So if we want 0 to 15 dollars
[log of 15 to base 2] + 1 = [3.90] + 1 = 3 + 1 = 4 boxes
we need to have 4 boxes each having 1,2,4,8, dollars respectively.Now we know from binary numbers that any amount from 0 to 15 can be formed with this boxes.
For 0 to 6 dollars
[log of 7 to base 2] + 1 = [2.58] + 1 = 2 + 1 = 3 boxes
we need to have 3 boxes each having 1,2,4, dollars respectively
For 0 to 100 dollars
[log of 100 to base 2] + 1 = [6.64] + 1 = 6 + 1 = 7 boxes
we need to have 7 boxes each having 1,2,4,8,16,32,64 dollars respectively
-Ameya Vaidya
No one mentioned why one should use binary numbers !!
Any numner n can be expressed in any base.
n = a1 * b^0 + a2 * b^1 + a3 * b^2 + …
where ai’s are from 0 to b-1.
eg. in decimal system
123 = 10^2 * 1 + 10 * 2 + 3.
In this case you either choose a box or not. So the ai’s can be 0 or 1.( 0 means dont choose and 1 means you chose it)
Hence b = 2;
So binary base has to be used.
max that you can represent using this is
2^b - 1 >=n;
It is the relation between b and n.
No one mention the restriction. Here it is.
2~0 + 2~1 + … + 2~b >= n
Otherwise it would be screwed.
The answer is
Give boxes(i) if (n & 2^i) is non zero
b0 * (n & 2^0) + b1* (n & 2^1) + b2* (n & 2^2) + … upto box(floor(log2(n)) + 1)
b should be atleast
b = floor(log2(n)) + 1;
b= log(n) + 1
{where log is computed to the base 2}
i feel the relation between n and b should be one-to-one.
n=b with each box having a dollar.
otherwise one cannot get one-to-one mapping between n and b.
As far as binary thing goes,(it still needs to keep non-exact amont in last box). If this is allowed then it can be done with just b=1. and putting all the amount asked in 1 box.
Why insisting on binary?
A distribution like :
1 dollar to Box#1
2 dollars to Box#2
3 dollars to Box#3
.. and so on, can do the trick.
With any combination of the boxes, any amount of money could be given.
And the restriction is,
n= (1+b)* b/2
You can represent in other bases too.
For e.g., base 3 (ie using 0, 1, 2) representation
Box 1, 2 put $1 (3^0)
Box 3, 4 put $3 (3^1)
Box 5, 6 put $9 (3^2)
i.e., choose a pair of boxes and put successive powers of 3 in each. When picking boxes for a given amount, first represent the number in base 3. Then based on what’s in each position (0, 1 or 2), pick that many boxes — dont pick a box (if 0), or pick one box (if 1), or pick two boxes (if 2).
Say you pick a base B. You have b/(B-1) positions. Then, make sure
(B ^ (b/(B-1))) - 1 >= n
If = n
if
johny’s answer is exact for base 2:
b >= floor(log2(n)) + 1;
Base 2 (binary) is also most efficient. The problem with other bases is you need additional boxes for each slot (e.g., 2×1,2×3,2×9,… for base 3). For binary, you only need 1 box for each slot (1,2,4,…).
Leave an Answer/Comment