Check if X can give change to every person in the Queue
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 for all people who are waiting to buy ice cream.
Examples:
Input:a[] = {5, 5, 5, 10, 20}
Output: YES
When the fourth person 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 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 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. |
Javascript
<script> // Javascript 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 function isChangeable(notes, n) { // To count the 5$ // and 10& notes let fiveCount = 0; let tenCount = 0; // Serve the customer // in order for (let 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; } // queue of customers // with available notes. let a = [5, 5, 5, 10, 20]; let n = a.length; // Calling function if (isChangeable(a, n) > 0) document.write( "YES" ); else document.write( "NO" ); </script> |
YES
Performance Analysis:
Time Complexity: O(n).
Space Complexity: O(1).