Given an array of N integers where Ai denotes the currency of note that the i-th person has. The possible currencies are 5, 10 and 20. All the N people are standing in a queue waiting to buy an ice-cream from X which costs Rs 5. Initially, X has an initial balance of 0. Check if X will be able to provide change to every people who are waiting to buy an ice-cream.
Examples:
Input:a[] = {5, 5, 5, 10, 20}
Output: YES
When the fourth person chance comes to buy an ice-cream, X has three Rs 5
change, hence X gives him 1, and now when the fifth person
comes to buy the ice-cream, X has two Rs 5 and one Rs 10 note, hence he
gives him one Rs 10 and one Rs 5 note.Input: a[] = {5, 10, 10, 20}
Output: NO
The approach is to keep a track of the number of Rs 5 and Rs 10 currencies. Rs 20 currencies will not be used since it is the highest currency that a person can give and thus it cannot be given as a change. Initialize two variables to count Rs 5(fiveCount) and Rs 10(tenCount). If the person has a Rs 10 currency and fiveCount > 0, then decrease fiveCount and increase tenCount. If X does not have Rs 5, then X cannot give the person the required change. If the person has 5$ note, increase fiveCount by one. If the person has a Rs 20, then three conditions will be:
- If fiveCount > 0 and tencount > 0, decrease both.
- else if, fiveCount >= 3, decrease fivecount by three.
- else, return false.
If all the person in the queue gets the change, then print “YES” else print “NO”.
Below is the implementation of the above idea.
C++
// C++ program to check whether X can give change // to every person in the Queue #include <bits/stdc++.h> using namespace std; // Function to check if every person will // get the change from X int isChangeable(int notes[], int n) { // To count the 5$ and 10& notes int fiveCount = 0; int tenCount = 0; // Serve the customer in order for (int i = 0; i < n; i++) { // Increase the number of 5$ note by one if (notes[i] == 5) fiveCount++; else if (notes[i] == 10) { // decrease the number of note 5$ and // increase 10$ note by one if (fiveCount > 0) { fiveCount--; tenCount++; } else return 0; } else { // decrease 5$ and 10$ note by one if (fiveCount > 0 && tenCount > 0) { fiveCount--; tenCount--; } // decrease 5$ note by three else if (fiveCount >= 3) { fiveCount -= 3; } else return 0; } } return 1; } // Driver Code int main() { // queue of customers with available notes. int a[] = { 5, 5, 5, 10, 20 }; int n = sizeof(a) / sizeof(a[0]); // Calling function if (isChangeable(a, n)) cout << "YES"; else cout << "NO"; return 0; } |
Java
// Java program to check // whether X can give // change to every person // in the Queue import java.io.*; class GFG { // Function to check if // every person will // get the change from X static int isChangeable(int notes[], int n) { // To count the 5$ // and 10& notes int fiveCount = 0; int tenCount = 0; // Serve the customer // in order for (int i = 0; i < n; i++) { // Increase the number // of 5$ note by one if (notes[i] == 5) fiveCount++; else if (notes[i] == 10) { // decrease the number // of note 5$ and // increase 10$ note by one if (fiveCount > 0) { fiveCount--; tenCount++; } else return 0; } else { // decrease 5$ and // 10$ note by one if (fiveCount > 0 && tenCount > 0) { fiveCount--; tenCount--; } // decrease 5$ // note by three else if (fiveCount >= 3) { fiveCount -= 3; } else return 0; } } return 1; } // Driver Code public static void main (String[] args) { // queue of customers // with available notes. int a[] = {5, 5, 5, 10, 20}; int n = a.length; // Calling function if (isChangeable(a, n) > 0) System.out.print("YES"); else System.out.print("NO"); } } // This code is contributed // by anuj_67. |
Python3
# Python program to check whether X can
# give change to every person in the Queue
# Function to check if every person
# will get the change from X
def isChangeable(notes, n):
# To count the 5$ and 10& notes
fiveCount = 0
tenCount = 0
# Serve the customer in order
for i in range(n):
# Increase the number of 5$ note by one
if (notes[i] == 5):
fiveCount += 1
elif(notes[i] == 10):
# decrease the number of note 5$
# and increase 10$ note by one
if (fiveCount > 0):
fiveCount -= 1
tenCount += 1
else:
return 0
else:
# decrease 5$ and 10$ note by one
if (fiveCount > 0 and tenCount > 0):
fiveCount -= 1
tenCount -= 1
# decrease 5$ note by three
elif (fiveCount >= 3):
fiveCount -= 3
else:
return 0
return 1
# Driver Code
# queue of customers with available notes.
a = [5, 5, 5, 10, 20 ]
n = len(a)
# Calling function
if (isChangeable(a, n)):
print(“YES”)
else:
print(“NO”)
# This code is contributed by PrinciRaj1992
C#
// C# program to check // whether X can give // change to every person // in the Queue using System; class GFG { // Function to check if // every person will // get the change from X static int isChangeable(int []notes, int n) { // To count the 5$ // and 10& notes int fiveCount = 0; int tenCount = 0; // Serve the customer // in order for (int i = 0; i < n; i++) { // Increase the number // of 5$ note by one if (notes[i] == 5) fiveCount++; else if (notes[i] == 10) { // decrease the number // of note 5$ and // increase 10$ note by one if (fiveCount > 0) { fiveCount--; tenCount++; } else return 0; } else { // decrease 5$ and // 10$ note by one if (fiveCount > 0 && tenCount > 0) { fiveCount--; tenCount--; } // decrease 5$ // note by three else if (fiveCount >= 3) { fiveCount -= 3; } else return 0; } } return 1; } // Driver Code public static void Main () { // queue of customers // with available notes. int []a = {5, 5, 5, 10, 20}; int n = a.Length; // Calling function if (isChangeable(a, n) > 0) Console.WriteLine("YES"); else Console.WriteLine("NO"); } } // This code is contributed // by anuj_67. |
YES
leave a comment
0 Comments