C Program for Philaland Coins Problem

July 2, 2020

Philaland Coin Problem

C program for Philaland Coins Problem is once of the solution for this problem, below on the page we have also provided the solution for this problem in Java and Python language, you can visit those pages too, if you want the solution in those specific pages.

C program for Philaland Coin Problem
All TCS CodeVita Questions with Answers

Problem Statement

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.

Let’s 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.

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

 

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

 

  • Constraints
    • 1<=T<=100
    • 1<=N<=5000

 

Refer the Sample Output Formatting

Sample Input:

      2
     10
      5

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

C Program for Philaland Coins Problem

#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;
}

Philaland Coin Problem in few other Coding Languages

Java

To find the solution of Philaland Coin Distribution Problem in Java Programming language click on the button below:

Java

C++

We don’t have the solution for this problem, you can contribute the answer of this code in C++ programming language, we post that answer on our page

Python

To find the solution of Philaland Coin Distribution Problem in Python Programming language click on the button below:

Python

4 comments on “C Program for Philaland Coins Problem”


  • Riyazur

    //An alternative solution….for c++(like if you find it easy)comment for any correction
    //thank you….
    #include
    using namespace std;
    int getz(int a);
    int main()
    {
    int t;
    cout<>t;
    int cas[t],i,j;
    for(i=0;i<t;i++)
    {
    cout<>cas[i];
    }
    for(j=0;j<t;j++)
    {
    cout<<"\n The min. values required for "<<cas[j]<<" is "<<getz(cas[j]);
    }

    }
    int getz(int a)
    {
    int counter=1,b=1;
    if(a==b)
    return counter;
    soln:
    a-=b;
    b++;
    counter+=1;

    if(a<=b)
    return counter;
    else{
    goto soln;

    }
    }


    • Riyazur

      website posting comment that is different from what i have wriiten..
      *
      *first 2 cout are cin>>
      *variable t is no. of test cases


  • Gaurav

    cpp soln

    #include
    #include
    using namespace std;
    int main()
    {
    int n;
    cin>>n;
    int five,one,two;
    five=floor((n-4)/5);
    if((n-5*five)%2==0)
    {
    one=2;
    }
    else{
    one=1;
    }
    two=floor((n-5*five-one)/2);
    printf(“%d %d %d %d”,five+two+one,five,two,one);
    }