Maximum number of people to be refunded with given coins
Given an array X[] of length N, Where X[i] for (1 ≤ i ≤ N) denotes the number of rupees we need to give to an ith person. Initially, we have P and Q numbers of coins of 1 Rs. and 2 Rs. respectively. Then your task is to output the maximum number of people, to whom you can return their money.
Note: You can’t give partial money to any person. For Example: If we need to return 5 Rs. and have Two 2 Rs. coins, Then you can’t return 4 Rs. to that person.
Examples:
Input: N = 5, P = 3, Q = 4, X[] = {3, 1, 4, 5, 1}
Output: 4
Explanation: We can return money to 1st, 2nd, 3rd and 5th person. Formally,
- X[1] = one 1 Rs. coin + one 2 Rs. coin = 1+2 = 3
- X[2] = one 1 Rs. coin = 1
- X[3] = two 2 Rs. coin = 4
- X[5] = one 1 Rs. coin = 1
We have returned money to 4 people by using three coins of 1 and 2 Rupees and left with one 2 Rs. coins. Hence, 4 is the maximum count of people to them we can return money.
Input: N = 7, P = 6, Q = 3, X[] = {4, 6, 1, 2, 3, 4, 1}
Output: 5
Explanation: It can be verified that we can return at maximum 5 person to their money.
Approach: To solve the problem follow the below idea:
The problem is based on the Greedy approach and sorting. We will try to return that amount of money first, which requires less number of coins. Therefore, elements of X[], which are smaller in values need to return first. So, we need to sort the X[]. We know that 2 Rs. coins can’t be used to return any odd amount, On the other hand 1 Rs. coin can be returned regardless of the value of amount. For Example: By 2 Rs. coins we can’t return amount 3 but same can be returned with three 1 Rs. coins. So, Greedy approach says that we have to save 1 Rs. coins as much possible and try to return amount with 2 Rs. coins first, after that using both 1 and 2 Rs. coins, in last check for only by 1 Rs. coins.
Illustration:
If amount to be return is 1, Then we can return it by 1 Rs. coin only, If we have at least one 1 Rs. coin. If amount to be return is 2, Then we can return it either by one 2 Rs. coin or two 1 Rs. coins. If possible then return it with one 2 Rs. coin first else check for two 1 Rs. coins. If amount to be return is greater than 2, check if amount if odd, check, If we return X[i] amount with 2 Rs. coins as X[i] – 1 and one 1 Rs. coin for remained 1.
- Example: X[i] = 9, amount (9-1) as 2 Rs. coins and remained 1 with 1 Rs. coin.
- If not possible by above condition, Then check available amount (P*2 + Q*1) ≥ X[i], Then set Q = 0 (Because for X[i] – 1 we have checked in previous condition, So in this condition there will be surely all 2 Rs. coins will be used for X[i] and the remained amount is paid by using 1 rs. coins).
- Example: X[i] = 9, Considered (9-5) can be paid by 2 Rs. coins and rest 5 with five 1 Rs. coins. So all two 2 Rs. coins are used for returning (9-5) amount. Therefore, set Q = 0.
- If not possible by above two conditions, Then we will check, If we can return the amount with 1 Rs. coins or not. Check, if amount is even, check If we can return amount by only 2 Rs. coins. If not possible with only by 2 Rs. coins, Then check for both 2 and 1 Rs. coins. In last, check if we can return it with only 1 Rs. coins or not.
Steps were taken to solve the problem:
- Create a variable max for storing the maximum number of people.
- Sort the array X[].
- Traverse on array X[],
- Check if (X[i] = 1)
- If(P ≥ 1), then decrement P and increment max.
- Check if (X[i] = 2)
- If(Q ≥ 1), then decrement Q and increment max.
- Else if (P ≥ 2), then decrement P by 2 and increment max.
- Check if (X[i] > 2)
- If X[i] is odd:
- If(Q ≥ (X[i]/2)), then Q -= (X[i]/2) and increment max.
- Else if(((Q * 2) + (P * 1)) ≥ X[i]), then X[i] -= (Q*2), P -= X[i], set Q to 0 and increment max.
- Else ((P ≥ X[i])), then P -= X[i] and increment max.
- If X[i] is even:
- if(Q ≥ ((X[i ] – 1)/2))
- if(P ≥ 1) then Q -= ((X[i] – 1)/2) and decrement P increment max.
- Else if(((Q*2) + (P*1)) ≥ X[i]), then X[i] -= Q*(2), P -= X[i], set Q = 0 and increment max.
- Else if(P ≥ X[i]), then P -= X[i] and increment max.
- if(Q ≥ ((X[i ] – 1)/2))
- If X[i] is odd:
- Check if (X[i] = 1)
- Output the value of max.
Below is the code for the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Method for returning the max number // of people to whom we can // return money void MaxReturn( int N, int P, int Q, int X[]) { // Variable to store max number // of people int max = 0; // Sorting X[] using in-built // Function of array class sort(X, X + N); // Loop for traversing over X for ( int i = 0; i < N; i++) { // If we need to return 1 Rs. // to a person then we can // give change in terms of // 1 Rs. coin only if (X[i] == 1) { // Checking that if we // have at least 1 coin // of 1 Rs. or not, If YES, // then minus count of 1 // Rs. coin and // incrementing people count if (P >= 1) { max++; P--; } } // If we need to return 2 Rs. // to a person then we can // give change in terms of two // 1 Rs. coin or one 2 Rs. coin else if (X[i] == 2) { // Checking that if we // have at least 1 coin // of 2 Rs. or not. If YES, // then minus count of 2 Rs. // coin and incrementing // people count if (Q >= 1) { Q--; max++; } // If we don't have 2 Rs. // coin Then we are // checking that if we // have at least two 1 Rs. // coin or not. If YES, // then minus count of 1 Rs. // coin by 2 and increment // people count. else if (P >= 2) { P -= 2; max++; } } // Else block, Executes when // we have to return money // Greater than 2 else { // If money to be return // is Even if (X[i] % 2 == 0) { // Checking that if we // can return in number // of 2 coins if (Q >= (X[i] / 2)) { Q -= (X[i] / 2); max++; } // If not have enough // 2 Rs. coins. Then // checking for combination // of 1 and 2 Rs. coins else if (((Q * 2) + (P * 1)) >= X[i]) { X[i] -= (Q * 2); Q = 0; P -= X[i]; max++; } // If above two conditions are not // satisfied Then checking, Whether we // can return money By 1 Rs. coins only // or not else if ((P >= X[i])) { P -= X[i]; max++; } } // Else block will execute when money to be // return is Odd else { // If we can return X[i] - 1 Rs. with 2 // Rs. coins Formally, if X[i] = 7, then // checking we can return // As three 2 Rs. coins and one 1 Rs. // coins. // Example : ((2*3)+1*1) = 7 if (Q >= ((X[i] - 1) / 2)) { if (P >= 1) { Q -= ((X[i] - 1) / 2); P--; max++; } } // Checking that If we can return X[i] // Rs. as combination of // 2 Rs. and 1 Rs. coins // This condition differs from above // conditon as: In above condition we // were returning X[i] - 1 Rs as 2 Rs. // coins. But in this condition we can't // do the same because 2 Rs. coins are // less Example : ((2*1)+1*5) = 7 We are // setting 2 Rs. coins count as 0 (Q = // 0), because all 2 Rs. coins will be // used in such condition else if (((Q * 2) + (P * 1)) >= X[i]) { X[i] -= (Q * 2); Q = 0; P -= X[i]; max++; } // this else block will execute if we // have can't return money by above // conditions Then checking that we can // return as sum of 1 Rs. coins or not. else { if (P >= X[i]) { P -= X[i]; max++; } } } } } // Printing the max number of people to whom // we can return money. cout << max; } // Driver Class int main() { // Inputs int N = 5; int P = 3, Q = 4; int X[] = { 3, 1, 4, 5, 1 }; // Function call MaxReturn(N, P, Q, X); } // This code is contributed by Tapesh(tapeshdua420) |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Driver Class public static void main(String[] args) throws java.lang.Exception { // Inputs int N = 5 ; int P = 3 , Q = 4 ; int X[] = { 3 , 1 , 4 , 5 , 1 }; // Function call MaxReturn(N, P, Q, X); } // Method for returning the max number // of people to whom we can // return money static void MaxReturn( int N, int P, int Q, int [] X) { // Variable to store max number // of people int max = 0 ; // Sorting X[] using in-built // Function of array class Arrays.sort(X); // Loop for traversing over X for ( int i = 0 ; i < N; i++) { // If we need to return 1 Rs. // to a person then we can // give change in terms of // 1 Rs. coin only if (X[i] == 1 ) { // Checking that if we // have at least 1 coin // of 1 Rs. or not, If YES, // then minus count of 1 // Rs. coin and // incrementing people count if (P >= 1 ) { max++; P--; } } // If we need to return 2 Rs. // to a person then we can // give change in terms of two // 1 Rs. coin or one 2 Rs. coin else if (X[i] == 2 ) { // Checking that if we // have at least 1 coin // of 2 Rs. or not. If YES, // then minus count of 2 Rs. // coin and incrementing // people count if (Q >= 1 ) { Q--; max++; } // If we don't have 2 Rs. // coin Then we are // checking that if we // have at least two 1 Rs. // coin or not. If YES, // then minus count of 1 Rs. // coin by 2 and increment // people count. else if (P >= 2 ) { P -= 2 ; max++; } } // Else block, Executes when // we have to return money // Greater than 2 else { // If money to be return // is Even if (X[i] % 2 == 0 ) { // Checking that if we // can return in number // of 2 coins if (Q >= (X[i] / 2 )) { Q -= (X[i] / 2 ); max++; } // If not have enough // 2 Rs. coins. Then // checking for combination // of 1 and 2 Rs. coins else if (((Q * 2 ) + (P * 1 )) >= X[i]) { X[i] -= (Q * 2 ); Q = 0 ; P -= X[i]; max++; } // If above two conditions are not // satisfied Then checking, Whether we // can return money By 1 Rs. coins only // or not else if ((P >= X[i])) { P -= X[i]; max++; } } // Else block will execute when money to be // return is Odd else { // If we can return X[i] - 1 Rs. with 2 // Rs. coins Formally, if X[i] = 7, then // checking we can return // As three 2 Rs. coins and one 1 Rs. // coins. // Example : ((2*3)+1*1) = 7 if (Q >= ((X[i] - 1 ) / 2 )) { if (P >= 1 ) { Q -= ((X[i] - 1 ) / 2 ); P--; max++; } } // Checking that If we can return X[i] // Rs. as combination of // 2 Rs. and 1 Rs. coins // This condition differs from above // conditon as: In above condition we // were returning X[i] - 1 Rs as 2 Rs. // coins. But in this condition we can't // do the same because 2 Rs. coins are // less Example : ((2*1)+1*5) = 7 We are // setting 2 Rs. coins count as 0 (Q = // 0), because all 2 Rs. coins will be // used in such condition else if (((Q * 2 ) + (P * 1 )) >= X[i]) { X[i] -= (Q * 2 ); Q = 0 ; P -= X[i]; max++; } // this else block will execute if we // have can't return money by above // conditions Then checking that we can // return as sum of 1 Rs. coins or not. else { if (P >= X[i]) { P -= X[i]; max++; } } } } } // Printing the max number of people to whom // we can return money. System.out.println(max); } } |
Python3
def MaxReturn(N, P, Q, X): max_people = 0 # Sorting the array of amounts X.sort() # Loop through each element in the # array X for i in range (N): if X[i] = = 1 : # If the amount is 1 if P > = 1 : max_people + = 1 P - = 1 elif X[i] = = 2 : # If the amount is 2 if Q > = 1 : max_people + = 1 Q - = 1 elif P > = 2 : max_people + = 1 P - = 2 else : # For amounts greater than 2 if X[i] % 2 = = 0 : # If the amount is even if Q > = (X[i] / / 2 ): max_people + = 1 Q - = X[i] / / 2 elif ((Q * 2 ) + (P * 1 )) > = X[i]: X[i] - = Q * 2 Q = 0 P - = X[i] max_people + = 1 elif P > = X[i]: P - = X[i] max_people + = 1 else : # If the amount is odd if Q > = ((X[i] - 1 ) / / 2 ) and P > = 1 : Q - = (X[i] - 1 ) / / 2 P - = 1 max_people + = 1 elif ((Q * 2 ) + (P * 1 )) > = X[i]: X[i] - = Q * 2 Q = 0 P - = X[i] max_people + = 1 elif P > = X[i]: P - = X[i] max_people + = 1 return max_people # Driver code N = 5 P = 3 Q = 4 X = [ 3 , 1 , 4 , 5 , 1 ] result = MaxReturn(N, P, Q, X) print (result) |
C#
// C# code to implement the approach using System; class GFG { // Method for returning the max number // of people to whom we can // return money static void MaxReturn( int N, int P, int Q, int [] X) { // Variable to store max number // of people int max = 0; // Sorting X[] using in-built // Function of array class Array.Sort(X); // Loop for traversing over X for ( int i = 0; i < N; i++) { // If we need to return 1 Rs. // to a person then we can // give change in terms of // 1 Rs. coin only if (X[i] == 1) { // Checking that if we // have at least 1 coin // of 1 Rs. or not, If YES, // then minus count of 1 // Rs. coin and // incrementing people count if (P >= 1) { max++; P--; } } // If we need to return 2 Rs. // to a person then we can // give change in terms of two // 1 Rs. coin or one 2 Rs. coin else if (X[i] == 2) { // Checking that if we // have at least 1 coin // of 2 Rs. or not. If YES, // then minus count of 2 Rs. // coin and incrementing // people count if (Q >= 1) { Q--; max++; } // If we don't have 2 Rs. // coin Then we are // checking that if we // have at least two 1 Rs. // coin or not. If YES, // then minus count of 1 Rs. // coin by 2 and increment // people count. else if (P >= 2) { P -= 2; max++; } } // Else block, Executes when // we have to return money // Greater than 2 else { // If money to be return // is Even if (X[i] % 2 == 0) { // Checking that if we // can return in number // of 2 coins if (Q >= (X[i] / 2)) { Q -= (X[i] / 2); max++; } // If not have enough // 2 Rs. coins. Then // checking for combination // of 1 and 2 Rs. coins else if (((Q * 2) + (P * 1)) >= X[i]) { X[i] -= (Q * 2); Q = 0; P -= X[i]; max++; } // If above two conditions are not // satisfied Then checking, Whether we // can return money By 1 Rs. coins only // or not else if ((P >= X[i])) { P -= X[i]; max++; } } // Else block will execute when money to be // return is Odd else { // If we can return X[i] - 1 Rs. with 2 // Rs. coins Formally, if X[i] = 7, then // checking we can return // As three 2 Rs. coins and one 1 Rs. // coins. // Example : ((2*3)+1*1) = 7 if (Q >= ((X[i] - 1) / 2)) { if (P >= 1) { Q -= ((X[i] - 1) / 2); P--; max++; } } // Checking that If we can return X[i] // Rs. as combination of // 2 Rs. and 1 Rs. coins // This condition differs from above // conditon as: In above condition we // were returning X[i] - 1 Rs as 2 Rs. // coins. But in this condition we can't // do the same because 2 Rs. coins are // less Example : ((2*1)+1*5) = 7 We are // setting 2 Rs. coins count as 0 (Q = // 0), because all 2 Rs. coins will be // used in such condition else if (((Q * 2) + (P * 1)) >= X[i]) { X[i] -= (Q * 2); Q = 0; P -= X[i]; max++; } // this else block will execute if we // have can't return money by above // conditions Then checking that we can // return as sum of 1 Rs. coins or not. else { if (P >= X[i]) { P -= X[i]; max++; } } } } } // Printing the max number of people to whom // we can return money. Console.WriteLine(max); } // Driver Class public static void Main( string [] args) { // Inputs int N = 5; int P = 3, Q = 4; int [] X = { 3, 1, 4, 5, 1 }; // Function call MaxReturn(N, P, Q, X); } } // This code is contributed by Utkarsh Kumar |
Javascript
// Javascript code to implement the approach // Method for returning the max number // of people to whom we can // return money function MaxReturn(N, P, Q, X) { // Variable to store max number // of people let max = 0; // Sorting X[] using in-built // Function X.sort((a, b) => a - b); // Loop for traversing over X for (let i = 0; i < N; i++) { // If we need to return 1 Rs. // to a person then we can // give change in terms of // 1 Rs. coin only if (X[i] == 1) { // Checking that if we // have at least 1 coin // of 1 Rs. or not, If YES, // then minus count of 1 // Rs. coin and // incrementing people count if (P >= 1) { max++; P--; } } // If we need to return 2 Rs. // to a person then we can // give change in terms of two // 1 Rs. coin or one 2 Rs. coin else if (X[i] == 2) { // Checking that if we // have at least 1 coin // of 2 Rs. or not. If YES, // then minus count of 2 Rs. // coin and incrementing // people count if (Q >= 1) { Q--; max++; } // If we don't have 2 Rs. // coin Then we are // checking that if we // have at least two 1 Rs. // coin or not. If YES, // then minus count of 1 Rs. // coin by 2 and increment // people count. else if (P >= 2) { P -= 2; max++; } } // Else block, Executes when // we have to return money // Greater than 2 else { // If money to be return // is Even if (X[i] % 2 == 0) { // Checking that if we // can return in number // of 2 coins if (Q >= Math.floor(X[i] / 2)) { Q -= Math.floor(X[i] / 2); max++; } // If not have enough // 2 Rs. coins. Then // checking for combination // of 1 and 2 Rs. coins else if (((Q * 2) + (P * 1)) >= X[i]) { X[i] -= (Q * 2); Q = 0; P -= X[i]; max++; } // If above two conditions are not // satisfied Then checking, Whether we // can return money By 1 Rs. coins only // or not else if ((P >= X[i])) { P -= X[i]; max++; } } // Else block will execute when money to be // return is Odd else { // If we can return X[i] - 1 Rs. with 2 // Rs. coins Formally, if X[i] = 7, then // checking we can return // As three 2 Rs. coins and one 1 Rs. // coins. // Example : ((2*3)+1*1) = 7 if (Q >= Math.floor((X[i] - 1) / 2)) { if (P >= 1) { Q -= Math.floor((X[i] - 1) / 2); P--; max++; } } // Checking that If we can return X[i] // Rs. as combination of // 2 Rs. and 1 Rs. coins // This condition differs from above // conditon as: In above condition we // were returning X[i] - 1 Rs as 2 Rs. // coins. But in this condition we can't // do the same because 2 Rs. coins are // less Example : ((2*1)+1*5) = 7 We are // setting 2 Rs. coins count as 0 (Q = // 0), because all 2 Rs. coins will be // used in such condition else if (((Q * 2) + (P * 1)) >= X[i]) { X[i] -= (Q * 2); Q = 0; P -= X[i]; max++; } // this else block will execute if we // have can't return money by above // conditions Then checking that we can // return as sum of 1 Rs. coins or not. else { if (P >= X[i]) { P -= X[i]; max++; } } } } } // Printing the max number of people to whom // we can return money. console.log(max); } // Driver Class // Inputs let N = 5; let P = 3, Q = 4; let X = [3, 1, 4, 5, 1]; // Function call MaxReturn(N, P, Q, X); // This code is contributed by Vaibhav Nandan |
4
Time Complexity: O(N*LogN), As sorting is performed.
Auxiliary Space: O(1)
Contact Us