TCS Codevita problem

harish_49 · July 5, 2019, 2:01pm

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?

rohit_mahale · July 5, 2019, 3:53pm

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 !

harish_49 · July 5, 2019, 4:07pm

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

Even i am writing on 12th of this month

rohit_mahale · July 5, 2019, 4:31pm

well,best of luck buddy !!

harish_49 · July 5, 2019, 4:53pm

Thanks wish you the same !

aert · July 5, 2019, 5:42pm

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.

l_returns · July 5, 2019, 5:59pm

This seems better and correct.

uttu316 · July 5, 2019, 6:22pm

Can you explain more why $5 coin did not consider? thank you

aert · July 5, 2019, 6:39pm

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

py_js · July 5, 2019, 7:25pm

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.

l_returns · July 6, 2019, 12:09am

19 in binary will be 10011
so 16 + 2 +1

dhirenlalwani9 · July 6, 2019, 4:20am

(log(N) base 2 ) + 1

bing_ambar · July 6, 2019, 2:30pm

What approach is needed for such questions?

projjal12 · July 6, 2019, 3:02pm

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

projjal12 · July 6, 2019, 3:07pm

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.

projjal12 · July 6, 2019, 3:10pm

How many questions are required to clear the round and get placed.
I solved 2 from zone 1 2019 edition.

Please reply

rishisharma · July 6, 2019, 3:22pm

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
.
.
.

l_returns · July 6, 2019, 4:18pm

my output is { 1,2,4,8,16} (size=5 hence ans=5) we can make all numbers from 0 to 31.

bing_ambar · July 7, 2019, 3:50pm

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

hitesh_pant · July 7, 2019, 4:34pm

this is the correct answer