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 distributing various 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
Example 1
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.
Program:
#include <stdio.h>
int sum(int x[],int l)
{
int j,s1=0;
for(j=1;j<=l;j++)
s1=s1+x[j];
return s1;
}
int main() {
int n,a[100],k=1,i,c,t,j;
scanf("%d",&t);
for(j=0;j<t;j++)
{
scanf("%d",&n);
a[1]=1;
c=0;
for(i=1;i<=n;i++)
{
if(i>sum(a,k))
{
k++;
a[i]=k;
}
}
for(i=1;i<=k;i++)
{
if(a[i]!=0)
c++;
}
printf("%d\n",c);
for(i=1;i<=k;i++)
a[i]=0;
k=1;
}
return 0;
}
You can also run it on an online IDE: https://ide.geeksforgeeks.org/CqdZa41BMI
Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!
Related Links:
import math
ReplyDeletefor _ in range(1,int(input())+1):
n=int(input())
c=0
while(math.pow(2,c)<=n):
c+=1
print(c)
How does it works?
DeleteEasy C++ Solution
ReplyDelete#include
using namespace std;
void dtob(int n)
{
int binArray[325];
int i = 0;
while(n > 0)
{
binArray[i] = n % 2;
n = n / 2;
i++;
}
cout<<"\n"<>testCase;
for(int j = 0; j < testCase; j++)
{
int n;
cin>>n;
dtob(n);
}
return 0;
}
def sum1(x,l):
ReplyDeletes1=0
for j in range(1,l):
s1=s1+x[j]
return s1
def main():
n=0
a=[]
k=1
c=0
t=0
t = int(input())
for _ in range(t):
n = int(input())
el = n+100
a = [0]*el
a[1]=1
c=0
for i in range(1,n+1):
if(i>sum1(a,k)):
k+=1
a[i]=k
for i in range(1,k+1):
if(a[i]!=0):
c+=1
print(c)
for i in range(1,k+1):
a[i]=0
k=1
return 0
main()
#include
ReplyDeleteint sum(int x[],int l)
{
int j,s1=0;
for(j=1;j<=l;j++)
s1=s1+x[j];
return s1;
}
int main() {
int n,a[100],k=1,i,c,t,j;
scanf("%d",&t);
for(j=0;jsum(a,k))
{
k++;
a[i]=k;
}
}
for(i=1;i<=k;i++)
{
if(a[i]!=0)
c++;
}
printf("%d\n",c);
for(i=1;i<=k;i++)
a[i]=0;
k=1;
}
return 0;
}