A special site for solving fun programming problems and challenges, interested in computer science, programming, basics, data structure and algorithms

 


Minimum number of coins Problem Code: MINCOINSSolvedSubmit (Practice)

Chef has infinite coins in denominations of rupees 5 and rupees 10.

Find the minimum number of coins Chef needs, to pay exactly X rupees. If it is impossible to pay X rupees in denominations of rupees 5 and 10 only, print 1.

Input Format

  • First line will contain T, number of test cases. Then the test cases follow.
  • Each test case contains of a single integer X.

Output Format

For each test case, print a single integer - the minimum number of coins Chef needs, to pay exactly X rupees. If it is impossible to pay X rupees in denominations of rupees 5 and 10 only, print 1.

Constraints

  • 1T1000
  • 1X1000

Subtasks

  • Subtask 1 (100 points): Original constraints.

Sample Input 1 

3
50
15
8

Sample Output 1 

5
2
-1

Explanation

Test Case 1: Chef would require at least 5 coins to pay 50 rupees. All these coins would be of rupees 10.

Test Case 2: Chef would require at least 2 coins to pay 15 rupees. Out of these, 1 coin would be of rupees 10 and 1 coin would be of rupees 5.

Test Case 3: Chef cannot pay exactly 8 rupees in denominations of rupees 5 and 10 only.


solution

#include<iostream>
using namespace std;

class solution
{
public:
	void solve()
	{
		int x;
		cin >> x;
		if (x % 5 != 0)
			cout << -1 << "\n";
		else
		{
			int r5, r10, rem;
			r5 = x / 5;
			r10 = r5 / 2;
			rem = r5 % 2;
			int ans = r10 + rem;
			cout << ans << "\n";
		}
	}
};
int main()
{
	solution ss;

	int t;
	cin >> t;
	while (t--)
    {
		ss.solve();
	}

	return 0;
}

No comments:

Post a Comment