Table of Contents
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.