Count ways to distribute exactly one coin to each worker
Given two arrays coins[] and salaries[] where coins[i] represents the value of ith coin and salaries[j] represents the minimum value of the coin that jth worker will accept. The task is to compute the number of ways to distribute exactly one coin to each worker. Since the answer can be large, print it modulo 109 + 7.
Examples:
Input: coins[] = {1, 2, 3}, salaries[] = {1, 2}
Output: 4
Explanation:
If the coin with value 1 is not used, then the remaining two coins are acceptable by both workers, contributing two possible ways to pay the workers.
If the coin with value 1 is used, then it can only be used for the first worker. Then either of the remaining coins can be used to pay the second worker. This also contributes to two possible ways.
Therefore, the four ways to pay the two workers are [2, 3], [3, 2], [1, 2], [1, 3].
Input: coins[] = {1, 2}, salaries[] = {2}
Output: 1
Approach: The idea is to use the Sorting and Two Pointers technique to solve the problem. Follow the steps below to solve the problem:
- Sort the salaries in descending order.
- Let f(i) be the number of coins used to pay the ith worker in the absence of any other workers. Since the salary[] array is sorted so the first worker demands the highest salary and the last worker demands the lowest salary. Therefore, the result is:
- For the function f(i), i is equal to the number of coins that are available to use to pay the current worker assuming that all previous workers have been paid.
- As the workers are sorted in non-increasing order of salaries, so any coin used to pay a former worker is guaranteed to be usable to pay the current worker. So the number of coins that can be used to pay the current worker will always be equal to f(i) ? i, independent of the previous choices made.
- To compute f(i) efficiently, use two pointers to track the number of coins that are currently valid.
- Print the total count of ways after all the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; // Function to find number of way to // distribute coins giving exactly one // coin to each person int solve(vector< int >& values, vector< int >& salary) { long long ret = 1; int amt = 0; // Sort the given arrays sort(values.begin(), values.end()); sort(salary.begin(), salary.end()); // Start from bigger salary while (salary.size()) { while (values.size() && values.back() >= salary.back()) { // Increment the amount amt++; values.pop_back(); } if (amt == 0) return 0; // Reduce amount of valid // coins by one each time ret *= amt--; ret %= MOD; salary.pop_back(); } // Return the result return ret; } // Driver code int main() { // Given two arrays vector< int > values{ 1, 2 }, salary{ 2 }; // Function Call cout << solve(values, salary); return 0; } |
Java
// Java program for // the above approach import java.util.*; class GFG{ static int MOD = 1000000007 ; // Function to find number of way to // distribute coins giving exactly one // coin to each person static int solve(Vector<Integer> values, Vector<Integer> salary) { int ret = 1 ; int amt = 0 ; // Sort the given arrays Collections.sort(values); Collections.sort(salary); // Start from bigger salary while (salary.size() > 0 ) { while (values.size() > 0 && values.get(values.size() - 1 ) >= salary.get(salary.size() - 1 )) { // Increment the amount amt++; values.remove(values.size() - 1 ); } if (amt == 0 ) return 0 ; // Reduce amount of valid // coins by one each time ret *= amt--; ret %= MOD; salary.remove(salary.size() - 1 ); } // Return the result return ret; } // Driver code public static void main(String[] args) { // Given two arrays Vector<Integer> values = new Vector<Integer>(); values.add( 1 ); values.add( 2 ); Vector<Integer> salary = new Vector<Integer>(); salary.add( 2 ); // Function Call System.out.print(solve(values, salary)); } } // This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach MOD = 1000000007 # Function to find number of way to # distribute coins giving exactly one # coin to each person def solve(values, salary): ret = 1 amt = 0 # Sort the given arrays values = sorted (values) salary = sorted (salary) # Start from bigger salary while ( len (salary) > 0 ): while (( len (values) and values[ - 1 ] > = salary[ - 1 ])): # Increment the amount amt + = 1 del values[ - 1 ] if (amt = = 0 ): return 0 # Reduce amount of valid # coins by one each time ret * = amt amt - = 1 ret % = MOD del salary[ - 1 ] # Return the result return ret # Driver code if __name__ = = '__main__' : # Given two arrays values = [ 1 , 2 ] salary = [ 2 ] # Function call print (solve(values, salary)) # This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approach using System; using System.Collections; class GFG{ static int MOD = 1000000007; // Function to find number of way to // distribute coins giving exactly one // coin to each person static int solve(ArrayList values, ArrayList salary) { int ret = 1; int amt = 0; // Sort the given arrays values.Sort(); salary.Sort(); // Start from bigger salary while (salary.Count > 0) { while (values.Count > 0 && ( int )values[values.Count - 1] >= ( int )salary[salary.Count - 1]) { // Increment the amount amt++; values.RemoveAt(values.Count - 1); } if (amt == 0) return 0; // Reduce amount of valid // coins by one each time ret *= amt--; ret %= MOD; salary.RemoveAt(salary.Count - 1); } // Return the result return ret; } // Driver code public static void Main( string [] args) { // Given two arrays ArrayList values = new ArrayList(); values.Add(1); values.Add(2); ArrayList salary = new ArrayList(); salary.Add(2); // Function Call Console.Write(solve(values, salary)); } } // This code is contributed by Rutvik_56 |
Javascript
<script> // Javascript program for the above approach var MOD = 1000000007; // Function to find number of way to // distribute coins giving exactly one // coin to each person function solve(values, salary) { var ret = 1; var amt = 0; // Sort the given arrays values.sort((a,b)=>a-b); salary.sort((a,b)=>a-b); // Start from bigger salary while (salary.length) { while (values.length && values[values.length-1] >= salary[salary.length-1]) { // Increment the amount amt++; values.pop(); } if (amt == 0) return 0; // Reduce amount of valid // coins by one each time ret *= amt--; ret %= MOD; salary.pop(); } // Return the result return ret; } // Driver code // Given two arrays var values = [1, 2 ], salary = [2]; // Function Call document.write( solve(values, salary)); // This code is contributed by itsok. </script> |
Output:
1
Time Complexity: O(N*log N)
Auxiliary Space: O(1)