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

## 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**

- Initialize three variables count5, count10 and count20 as 0.
- Traverse the given array.
- If arr[i] is 5, increment count5 by 1.
- 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.
- 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.
- 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.