Find minimum number of coins required to form any value between 1 to N, both inclusive. Cumulative value of coins should not exceed N. Coin denominations are 1 Rupee, 2 Rupee and 5 Rupee.
Lets understand the problem using the following example.
Consider value of N is 13, then the minimum number of coins required to formulate any value between 1 and 13, is 6. One 5 Rupee, three 2 Rupee and two 1 Rupee coins are required to realize any value between 1 and 13. Hence this is the answer.
However, if one takes two 5 Rupee coins, one 2 rupee coin and two 1 rupee coin, then too all values between 1 and 13 are achieved. But since the cumulative value of all coins equals 14, i.e., exceeds 13, this is not the answer.
Constraints
0 < n < 100000
Input Format
A single integer value.
Output
Four space separated integer values.
1st – Total number of coins.
2nd – number of 5 Rupee coins.
3rd – number of 2 Rupee coins.
4th – number of 1 Rupee coins.
Test Case
Input
13
Output
6 1 3 2
Explanation
The minimum number of coins required is 6 with in it:
minimum number of 5 Rupee coins = 1
minimum number of 2 Rupee coins = 3
minimum number of 1 Rupee coins = 2
Using these coins, we can form any value with in the given value and itself, like below:
Here the given value is 13
For 1 = one 1 Rupee coin
For 2 = one 2 Rupee coin
For 3 = one 1 Rupee coin and one 2 Rupee coins
For 4 = two 2 Rupee coins
For 5 = one 5 Rupee coin
For 6 = one 5 Rupee and one 1 Rupee coins
For 7 = one 5 Rupee and one 2 Rupee coins
For 8 = one 5 Rupee, one 2 Rupee and one 1 Rupee coins
For 9 = one 5 Rupee and two 2 Rupee coins
For 10 = one 5 Rupee, two 2 Rupee and one 1 Rupee coins
For 11 = one 5 Rupee, two 2 Rupee and two 1 Rupee coins
For 12 = one 5 Rupee, three 2 Rupee and one 1 Rupee coins
For 13 = one 5 Rupee, three 2 Rupee and two 1 Rupee coins
public class HelloWorld{
public static void main(String []args){
int five=0;
int one=0;
int two=0;
int number=3;
int original=number;
int dummy=number;
while(((dummy-4)%5)!=0){
dummy– ;
}
five=(dummy-4)/5;
if(five<0)
five=0;
number=number-(5*five);
if(number%2==0){
one=2;
}
else{
one=1;
}
two=(original-(one+(5*five)))/2;
System.out.println("ones="+ one+" twos= "+two+" FIVES= "+five);
}
}
what logic are you using to calculate the no of rs 5 coins?
lol very simple
n = int(input())
five = two = one = 0
temp = n
while temp % 5 != 0:
temp -= 1
five = (temp//5) – 1
temp = n – (5*five)
if temp % 2 == 0:
one = 2
else:
one = 1
temp -= one
two = temp//2
print((five+two+one), five, two, one)
#include
using namespace std;
int main(){
int n;
cin >> n;
int one = 0;
int two = 0;
int five = (n-4)/5;
if(five%2 ^ n%2)
one = 1;
else
one = 2;
two = (n – five*5 – one)/2;
cout << one+two+five << " " << five << " " << two << " " << one << endl;
return 0;
}