Thanks 
wish you the same !
I think the answer will be log(N)+1 as 20 is possible with $1, $2, $4, $8, $16.
It is probably possible to prove this recursively.
6 Likes
This seems better and correct.
1 Like
Can you explain more why $5 coin did not consider? thank you
You can think of this in binary.
In the binary representation of each number if the bit is 1 then we include it.
Eg. 20 in binary is 10100 which is the same as 1 * 16 + 0 * 8 + 1 * 4 + 0 * 2 + 0 * 1
2 Likes
But how can we handle case for 19?
As we need exact 19 using coins.
so - 16+3 may be required here.
Please correct me.
19 in binary will be 10011
so 16 + 2 +1
(log(N) base 2 ) + 1
2 Likes
What approach is needed for such questions?
1 Like
Basically, run a for-loop from 1(lowest currency) till the sum of loop variables is less than the max currency. Where the loop exits just subtract 1 and print the loop variable value.
Say I want 21 to be the max currency denomination, so by my analogy the currency dist is {1,2,3,4,5,6}.
Take the (max sum)=21
Basically my goal is to limit no. of coins to achieve max target.
Cheers
1 Like
But the problem basically says, you can obtain any no. in given test case between output’s max and min (1) interval.
Say your answer is no. of bits of that no.
I say 21.
So input is {1…21}
Now 21 has binary= 10101
Length=5
So output={1…5}
But adding all dist no (as the problem says 1 coin 1 time) max sum=1+…+5=15
We can’t even obtain 21 mate.
How many questions are required to clear the round and get placed.
I solved 2 from zone 1 2019 edition.
Please reply
I think following logic should solve this-
The logic is that we can generate any number using the combination of powers of 2
1=2^0
2=2^1
3=2^0+2^1
4=2^2
5=2^2+2^0
6=2^2+2^1
7=2^2+2^1+2^0
.
.
.
my output is { 1,2,4,8,16} (size=5 hence ans=5) we can make all numbers from 0 to 31.
1 Like
If you solve 2 questions you’ll definitely be called for the interview. Solving 2 questions yields you a rank of 3000 possibly.
This \log_2(N)+1 only.
4 Likes
@bing_ambar, the approach needed for such questions is trying to generate the numbers. When you start with $1 onwards, you will find that you need $1 and $2 and then you will come to know that $3 is not required since we can generate it from $1 and $2. Then, you will eventually need $4 as it can not be generated in any way with the existing coins. Now that $4 is present, you already know that you can generate all values from $1 to $3, which means 4+(1 or 2 or 3) can also be generated, i.e., upto $7 can be generated. Now, the new coin required would be $8. Now, using the same technique, we know that we could generate all values between 1 and 7, and hence, 8 + (1 to 7) gives us all values between 1 and 15 and then the new coin required would be $16.
If you keenly observe, there is a pattern, 1, 2, 4, 8, 16, 32, 64, …
Hope you now understood why it is (1 + floor(log(N, 2))
16 Likes
Somebody please tell, in codevita all the inputs are valid or we also have to taken care of that??
Till now there has not been any such instances .So ,all the inputs will be valid.