Tutorialspoint.dev

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

Output:

YES


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter