TCS Codevita problem

Philaland Coin

Problem Description
The problem solvers have found a new Island for coding and named it as Philaland.These smart people were given a task to make purchase of items at the Island easier by distributingvarious coins with different value.Manish has come up with a solution that if we make coins category starting from $1 till the maximum price of item present on Island, then we can purchase any item easily. He added
following example to prove his point.

Lets suppose the maximum price of an item is 5$ then we can make coins of {$1, $2, $3, $4, $5}
to purchase any item ranging from $1 till $5.
Now Manisha, being a keen observer suggested that we could actually minimize the number of coins required and gave following distribution {$1, $2, $3}. According to him any item can be purchased one time ranging from $1 to $5. Everyone was impressed with both of them.

Your task is to help Manisha come up with minimum number of denominations for any arbitrary max price in Philaland.
Constraints
1<=T<=100
1<=N<=5000

Input Format
First line contains an integer T denoting the number of test cases.
Next T lines contains an integer N denoting the maximum price of the item present on Philaland.

Output
For each test case print a single line denoting the minimum number of denominations of coins required.

Test Case
Input
2
10
5

Output
4
3

Explanation
For test case 1, N=10.
According to Manish {$1, $2, $3,… $10} must be distributed.
But as per Manisha only {$1, $2, $3, $4} coins are enough to purchase any item ranging from $1 to $10. Hence minimum is 4. Likewise denominations could also be {$1, $2, $3, $5}. Hence answer is still 4.

For test case 2, N=5.
According to Manish {$1, $2, $3, $4, $5} must be distributed.
But as per Manisha only {$1, $2, $3} coins are enough to purchase any item ranging from $1 to $5. Hence minimum is 3. Likewise denominations could also be {$1, $2, $4}. Hence answer is still 3.

Can some one please suggest me a correct approach to solve it?

2 Likes

i also participated in code-vita this year and im in zone 2 which will be on 12 this month!
i have found this question before 2-3 days and what i was thing is -

lets n=20 so we are just starting with 1$ and increasing it it the sum of all the dollar’s crosses 20 !!
in this case we will be having 1$,2$,3$,4$,5$,6$ and sum of these dollar’s will be 21 and i guess you can buy and item in between 1 to 20. i don’t know it gonna work i was thinking in this statement !!
suggestion will take a place of appreciation !

Yeah , even i too thought of same but i posted just to confirm whether there is any dp related stuff :stuck_out_tongue:

Even i am writing on 12th of this month :slight_smile:

well,best of luck buddy !!

Thanks :slight_smile: 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.

This seems better and correct.

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

1 Like

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

What approach is needed for such questions?

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

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.

If you solve 2 questions you’ll definitely be called for the interview. Solving 2 questions yields you a rank of 3000 possibly.


this is the correct answer