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.
CODE
import java.io.*;
public class Main
{
public static void main(String[] args)throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
int x=0;
while(Math.pow(2,x)<=n){
x++;
}
System.out.println(x);
}
}
import java.io.*;
public class Main
{
public static void main(String[] args)throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
int x=0;
while(Math.pow(2,x)<=n){
x++;
}
System.out.println(x);
}
}
output is not coming why so??
The answer is log(n)base 2 +1.
Many of you like me, may scratch your head that how did we get to this conclusion.
think it in this way,
how many possible ways are there to create $1 ?
using 1 coin.
how many possible ways are there to create $2 ?
using two one coins or one 2 coin.
we could have taken two $1 coins also, but we are taking one $2 coin, because we can not repeat coins, rules are rules mate, can’t do much.
for 3 we can use a single $3 coin, but we can make three from previous available coins without replications.[$1+$2=$3, see a Mathematician here]
But for $4 we can’t do the same, we need to use either $1 coins 4 times, or $2 coins twice.
So we introduce $4 coin [BLOODY RULES,].
with $1 ,$2 and $4 coins we can obtain $5,$6,$7 but for $8 we need to do duplication of at least one coin and that’s against the rules of the game[Don’t curse me, I didn’t make rules].
from $1, $2, $4, $8 coins we can make $9, $10, $11, $12, $13, $14 and $15, but not $16 without duplicating any of the previous coins.
So we introduce a $16 coin
Now can you see something?
1 is 2^0
2 is 2^1
4 is 2^2
8 is 2^3
16 is 2^4
we are lucky that we have number one with us because we obtain odd numbers from it and for even numbers 2 and its powers are enough.
So, lets take example of hundred.$100
2^6 is the smallest power of two before the number hundred.
2^6=64,,,,,,,,,,,,2^7 is 128>100[Mathematician here]
Now we have 100-64=36
2^5=32
36-32=4
2^2=4
so we got hundred with 64 32 and 4, so let us put them in our bag[4,32,64]
But what about other numbers?
like we can not get 50 with this?
Yes, we can not get 50,43, or some random number from 64,32, and 4.
But to get 1 we need 1. so we add 1 to our bag. [1,4,32,64].
What about 2?
let us put that in our bag as well[1,2,4,32,64]
we can make 5,6,7 with our bag but we can not make 8, so it us put it there.
[1,2,4,8,32,64]
now we can get numbers from 9 to 15,but not 16. No worries let us put that ass well
[1,2,4,8,16,32,64].
So can we get a given number lets say 93?
probably with 64,16,8,4 and 1?
If this comment helped you, please support my youtube channel where I make short film
Philaland Coin
why the code doesnt work for the code given below; please provide me a solution of this by corecting my code :
if(Math.pow(2,a)>= n)
System.out.println(a);
else
a++;
Thank You very much for ur Explination
its all a magic of binary representation……no doubt first thought came to my mind my that using binary representation we can generate any number….but i guess its not working in the tcs codevita practice session……..don;t know why. ….compiler saying wrong answer;
for n=1, the pow(2,0) =1
your if condition is true as pow(2,0) >= n, Thus it will print 0 which is wrong answer..the answer should be 1
for _ in range(int(input())):
x= int(input())
i=0
while 2**i <= x:
i+=1
print(i)
t = int(input())
for i in range(t):
n = int(input())
j = 0
k = 0
while j < n:
k+=1
j+=k
print(k)
Can this will work ??????
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int count=0;
for(int i=1;i=a)
{
System.out.println(i-1);
break;
}
else{
count=count+i;
}
}
}
}
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int count=0;
for(int i=1 ; i=a)
{
System.out.println(i-1);
break;
}
else{
count=count+i;
}
}
}
}
If I try This code it is showing error .
Pls Help.
Philaland.c 2 1 error unknown type name import import java.util.*; ^ Philaland.c 2 12 error expected = ; asm or __attribute__ before . token import java.util.*; ^ Philaland.c 3 1 error unknown type name public public class Main ^ Philaland.c 3 14 error expected = ; asm or __attribute__ before Main public class Main ^ Philaland.c 19 1 error expected identifier or before } token } ^
It is showing the error as shown above
t=int(input())
print(“\n”)
for i in range(t):
n=int(input())
count=1
if n==1:
print(1)
elif n1:
n=n//2
count+=1
print(count)
print(“\n”)
print(“\n”)
Output:-
4
-34
wrong input!
0
wrong input!
5
3
10
4
minimum number of denominations for an arbitrary sum is the number of digits of their binary representation .
t = int(input())
for z in range(t):
n = int(input())
count = 1
total_val = 1
while total_val <= n:
total_val = (2*total_val) + 1
count += 1
print(count)
inline void solve()
{
fast();
int n;
cin >> n;
/* using Sridhar Acharya Extended Formula –> constant time and constant space */
int form = ceil((-1 + sqrt(1 + 8 * n)) / 2);
cout << form << dl;
}