Minimum removal of people to equalize the number of coins
Given an array X[] of length N. This denotes that ith person has X[i] coins, the task is to output the minimum number of people needed to remove so that, the remaining person will have an equal number of coins. While removing ith person, the below operations will take place, consider that he has X[i] coins, then:
- That ith person will be removed from X[]
- He can choose an integer let’s say A (0 <= A <= X[i]).
- He will distribute A number of coins to the remaining people of X[] (It is not necessary to equally distribute coins and also not necessary to give each remaining person as well). Formally, distribution to any number of remaining people and any number of coins from A.
- The removed ith person will take (X[i] – A) coins with him.
Examples:
Input: N = 5, X[] = {2, 1, 2, 1, 1}
Output: 2
Explanation:
- First removed person will be i = 1, He has X[1] = 1 coins and selects A = 0. It means he will distribute 0 coins to remaining 4 persons in X[] and will take X[1] – 0 = 1 coins with him. So, Now updated X[] is: {2, 2, 1, 1}
- Second removed person will be i = 1 from updated X[]. He has X[1] = 2 coins with him. He choose A = 2, means will distribute his 2 coins among any number of person from remaining ones. He gives 1 coin each X[2] and X[3] and take X[1] – 2 = 0 coins with him. Now, updated X[] is: {2, 2, 2}
Now, It can be verified that X[] has equal number of coins on remaining 3 persons. Therefore, minimum number of persons needed to remove are 2.
Input: N = 3, X[] = {4, 4, 4}
Output: 0
Explanation: It can be seen that, all persons has already equal number of coins. Therefore, no need to remove any person.
Approach: Implement the approach to solve the problem
The problem is based on Greedy approach and can be solved by Sorting X[].
For equalizing X[], we have to make all the array element equal to the largest element of the array.
For Example let say X[] = {1, 1, 2, 3, 3, 4}
At beginning all the elements are not equal so we will decide to make all the element equal. If we remove 4 then we have to make all the elements equal to 3 because making all elements equal to 3 will require least values.
Formally, it will require:
((max element * total present element) – sum of the remaining element)
here we have, 5*3 – 10 = 5
So, we have to consider remove this 3 also.
then required = 3*4 – 7 = 5… And the persons we have removed are having 3 + 5 coins. Therefore, we have to remove 2 persons.
Steps were taken to solve the problem:
- Declare the variables Ans, Sum and Max and initialize them equal to 0, 0, and Int_min respectively.
- Sort(X)
- Declare a variable let say have.
- Run a loop for i = N – 1 and i > 0 and follow below mentioned steps under the scope of loop
- have += X[i]
- present_sum = sum – have
- req = (i*X[i-1]) – present_sum
- Ans++
- if (have >= req)
- break the loop
- Output ans;
Code to implement the approach:
C++
// C++ code contributed by Flutterfly #include <iostream> #include <algorithm> using namespace std; // Method to output the minimum // number of person void minimumPeople( int N, int X[]) { // Variable to store ans, sum and max // elements resectively int ans = 0; int sum = 0; int max = -1e9; for ( int i = 0; i < N; i++) { sum += X[i]; max = X[i] > max ? X[i] : max; } // Sorting X[] sort(X, X + N); // Implementing the discussed approach int have = 0; for ( int i = N - 1; i > 0; i--) { have += X[i]; int presentSum = sum - have; int required = i * X[i - 1] - presentSum; ans++; if (have >= required) { break ; } } // Printing the minimum number // of people to remove cout << ans << endl; } // Driver Code int main() { // Inputs int N = 5; int X[] = {2, 1, 2, 1, 1}; // Function call minimumPeople(N, X); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver Class public class Main { // Driver Function public static void main(String[] args) { // Inputs int N = 5 ; int X[] = { 2 , 1 , 2 , 1 , 1 }; // Function call Minimum_people(N, X); } // Method to output the minimum // number of person public static void Minimum_people( int N, int [] X) { // Variable to store ans, sum and max // elements resectively int ans = 0 , sum = 0 , max = Integer.MIN_VALUE; for ( int i = 0 ; i < N; i++) { sum += X[i]; max = X[i] > max ? X[i] : max; } // Sorting X[] Arrays.sort(X); // Implementing the discussed approach long have = 0 ; for ( int i = N - 1 ; i > 0 ; i--) { have += X[i]; long present_sum = sum - have; long req = (i * X[i - 1 ]) - present_sum; ans++; if (have >= req) { break ; } } // Printing the minimum number // of people to remove System.out.println(ans); } } |
Python
# code contributed by Flutterfly def main(): # Inputs N = 5 X = [ 2 , 1 , 2 , 1 , 1 ] #Function call minimum_people(N, X) #Method to output the minimum # number of person def minimum_people(N, X): # Variable to store ans, sum and max # elements resectively ans = 0 sum = 0 max = float ( '-inf' ) for i in range (N): sum + = X[i] max = X[i] if X[i] > max else max #Sorting X[] X.sort() #Implementing the discussed approach have = 0 for i in range (N - 1 , 0 , - 1 ): have + = X[i] present_sum = sum - have req = (i * X[i - 1 ]) - present_sum ans + = 1 if have > = req: break #Printing the minimum number # of people to remove print (ans) if __name__ = = "__main__" : main() |
C#
using System; // Driver Class public class GFG { // Driver Function public static void Main( string [] args) { // Inputs int N = 5; int [] X = { 2, 1, 2, 1, 1 }; // Function call Minimum_people(N, X); } // Method to output the minimum // number of person public static void Minimum_people( int N, int [] X) { // Variable to store ans, sum and max // elements resectively int ans = 0, sum = 0, max = int .MinValue; for ( int i = 0; i < N; i++) { sum += X[i]; max = X[i] > max ? X[i] : max; } // Sorting X[] Array.Sort(X); // Implementing the discussed approach long have = 0; for ( int i = N - 1; i > 0; i--) { have += X[i]; long present_sum = sum - have; long req = ( long )i * X[i - 1] - present_sum; ans++; if (have >= req) { break ; } } //Printing the minimum number // of people to remove Console.WriteLine(ans); } } |
Javascript
// JavaScript code to implement the approach //Driver Code // Inputs let N = 5; let X = [2, 1, 2, 1, 1]; // Function call minimumPeople(N, X); // Method to output the minimum // number of person function minimumPeople(N, X) { // Variable to store ans, sum and max // elements resectively let ans = 0; let sum = 0; let max = -Infinity; for (let i = 0; i < N; i++) { sum += X[i]; max = X[i] > max ? X[i] : max; } // Sorting X[] X.sort((a, b) => a - b); // Implementing the discussed approach let have = 0; for (let i = N - 1; i > 0; i--) { have += X[i]; let presentSum = sum - have; let required = i * X[i - 1] - presentSum; ans++; if (have >= required) { break ; } } // Printing the minimum number // of people to remove console.log(ans); } |
2
Time Complexity: O(N)
Auxiliary space: O(N)
Contact Us