Check if X can give change to every person in the Queue

Difficulty Level Medium
Frequently asked in Amazon
QueueViews 1147

Problem Statement

X is an ice cream seller and there are n people waiting in a queue to buy an ice cream. Arr[i] denotes the denomination ith person in the queue has, the possible values of denominations are 5, 10 and 20. If the initial balance of X is 0 and the cost of an ice cream is 5. Then determine whether or not X will be able to give change to all the people standing in the queue? Thus the problem is “Check if X can give change to every person in the Queue”.

Check if X can give change to every person in the Queue

Examples

arr[] = {5, 5, 10, 20}
true
arr[] = {10, 5, 5, 5, 5, 5}
false
arr[] = {5, 5, 5, 20, 5, 10}
true

Algorithm to Check if X can give change to every person in the Queue

Idea

The idea is to keep the track of denominations of 5, 10 and 20 that X has. Let these be represented by count5, count10 and count20. It is always optimal to return change with as high value currency as possible. There are total three cases,

  • arr[i] = 5,
    increment count5 by 1
  • arr[i] = 10,
    If count5 > 0, increment count10 by 1 and decrement count5 by 1
  • arr[i] = 20,
    If count10 > 0 and count5 > 0, increment count20 by 1, decrement count10 and count5 by 1.
    Else if count5 > 2, increment count20 by 1, decrement count5 by 3

Approach

  1. Initialize three variables count5, count10 and count20 as 0.
  2. Traverse the given array.
  3. If arr[i] is 5, increment count5 by 1.
  4. Else if arr[i] is 10, check if count5 > 0, if yes, increment count10 by 1 and decrement count5 by 1, else X cannot give change to all the customers, return false.
  5. Else if arr[i] is 20, check if count10 is greater than 0 and count5 is greater than 0. If yes, increment count20 by 1 and decrement count5 and count10 by one, if not, check if count5 is greater than 2, if yes, increment count20 by 1 and decrement count5 by 3, else X cannot give change to all the customers, return false.
  6. If X was able to return change to all the customers, return true.

Code

Java code to Check if X can give change to every person in the Queue

class CheckIfXCanGiveChangeToEveryPersonStandingInQueue {
    private static boolean checkIfPossible(int[] arr) {
        // initialize count0, counnt10 and count20 as 0
        int count5 = 0, count10 = 0, count20 = 0;
        
        // traverse in the array
        for (int i = 0; i < arr.length; i++) {
            // Case 1 : arr[i] = 5
            if (arr[i] == 5) {
                // increment count5 by 1
                count5++;
            }
            // Case 2 : arr[i] = 10
            else if (arr[i] == 10) {
                // if there are some 5 rs coins return 1
                if (count5 > 0) {
                    // decrement count5 by 1 and increment count10 by 1
                    count5--;
                    count10++;
                } else {
                    // if there are not, X cannot give change to everyone
                    return false;
                }
            }
            // Case 3 : arr[i] = 20
            else {
                // if there are some 10 rs coins and some 5 rs coin return one one each
                if (count10 > 0 && count5 > 0) {
                    count10--;
                    count5--;
                    count20++;
                } else if (count5 > 2) {
                    // else if there are 3 or more 5 rs coins return 3
                    count5 -= 3;
                    count20++;
                } else {
                    // X cannot give chnage to everyone
                    return false;
                }
            }
        }

        // X can give change to everyone
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 5, 10, 20};
        System.out.println(checkIfPossible(arr1));

        // Example 2
        int arr2[] = new int[] {10, 5, 5, 5, 5, 5};
        System.out.println(checkIfPossible(arr2));

        // Example 3
        int arr3[] = new int[]{5, 5, 5, 20, 5, 10};
        System.out.println(checkIfPossible(arr3));
    }
}
true
false
true

C++ Code to Check if X can give change to every person in the Queue

#include<bits/stdc++.h> 
using namespace std; 

bool checkIfPossible(int *arr, int n) {
    // initialize count0, count10 and count20 as 0
    int count5 = 0, count10 = 0, count20 = 0;

    // traverse in the array
    for (int i = 0; i < n; i++) {
        // Case 1 : arr[i] = 5
        if (arr[i] == 5) {
            // increment count5 by 1
            count5++;
        }
        // Case 2 : arr[i] = 10
        else if (arr[i] == 10) {
            // if there are some 5 rs coins return 1
            if (count5 > 0) {
                // decrement count5 by 1 and increment count10 by 1
                count5--;
                count10++;
            } else {
                // if there are not, X cannot give change to everyone
                return false;
            }
        }
        // Case 3 : arr[i] = 20
        else {
            // if there are some 10 rs coins and some 5 rs coin return one one each
            if (count10 > 0 && count5 > 0) {
                count10--;
                count5--;
                count20++;
            } else if (count5 > 2) {
                // else if there are 3 or more 5 rs coins return 3
                count5 -= 3;
                count20++;
            } else {
                // X cannot give chnage to everyone
                return false;
            }
        }
    }

    // X can give change to everyone
    return true;
}

int main() {
    // Example 1
    int arr1[] = {5, 5, 10, 20};
    if (checkIfPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    int arr2[] = {10, 5, 5, 5, 5, 5};
    if (checkIfPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    int arr3[] = {5, 5, 5, 20, 5, 10};
    if (checkIfPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
}
true
false
true

Complexity Analysis

Time Complexity 

O(n), because we have traversed through the input array having n elements. And this made the algorithm to run in linear time.

Space Complexity

O(1), because we have not used any array. We have use donly 3 variables which takes constant space. And thus constant space complexity.
where n is the total number of customers.

Translate »