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

Difficulty Level Medium
Queue

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

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.