Minimum number of operations required to make all elements equal
Given an array arr[] of length N along with an integer M. All the elements of arr[] are in the range [1, N]. Then your task is to output the minimum number of operations required to make all elements equal given that in one operation you can select at most M elements and increment all of them by 1.
Examples:
Input: N = 3, M = 2, arr[] = {1, 2, 3}
Output: 2
Explanation: Initially arr[] = {1, 2, 3} and we can select at most 2 elements to increment. Then the operations are performed as follows:
- 1st operation: Select A1 and A2 and increment them by 1. Then, updated arr[] = {2, 3, 3}
- 2nd operation: Select A1 and increment them by 1. Then, updated arr[] = {3, 3, 3}
All the elements are equal and number of operations applied are 2. Which is minimum possible.
Input: N = 4 M = 1, arr[] = {1, 1, 2, 2}
Output: 2
Explanation: It can be verified that the minimum number of operations required will be 2.
Approach: To solve the problem, follow the below idea:
The problem is based on the Greedy logic. The following steps can be taken to solve the problem:
- First, we have to find maximum and minimum elements of arr[] in two variables let say Max and Min.
- Then calculate the sum of differences of all elements with maximum element and store it in a variable let say Sum.
- Then the required answer will be: max(Max-Min, Ciel(Sum/M).
Step-by-step algorithm:
- Declare a variable let say Max and store the maximum element of arr[] in it.
- Declare a variable let say Min and store the minimum element of arr[] in it.
- Calculate the sum of differences of all elements with Max in a variable let say Sum
- Output max(Max-Min, (Sum+M-1)/M)).
Below is the implementation of the algorithm:
C++
#include <iostream> #include <algorithm> using namespace std; // Function to output the minimum number of operations required void MinOperations( int N, long M, long arr[]) { // Variable storing max element of A[] long Max = *max_element(arr, arr + N); // Variable to store the sum of differences long Sum = 0; // Variable storing min element of A[] long Min = *min_element(arr, arr + N); // Calculating sum of differences with max element for ( int i = 0; i < N; i++) { Sum += (Max - arr[i]); } // Printing the required minimum operations cout << max(Max - Min, (Sum + M - 1) / M) << endl; } // Driver Function int main() { // Inputs int N = 3; long M = 2; long arr[] = {1, 2, 3}; // Function call MinOperations(N, M, arr); return 0; } // This code is contributed by akshitaguprzj3 |
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 = 3 ; long M = 2 ; long [] arr = { 1 , 2 , 3 }; // Function call MinOperations(N, M, arr); } // Method to output the minimum number of operations // required public static void MinOperations( int N, long M, long [] arr) { // Variable storing max element of A[] long Max = Arrays.stream(arr).max().getAsLong(); // Variable to store the sum of differences long Sum = 0 ; // Variable storing min element of A[] long Min = Arrays.stream(arr).min().getAsLong(); // Calculating sum of differences with max element for ( int i = 0 ; i < N; i++) { Sum += (Max - arr[i]); } // Printing the required minimum operations System.out.println(Math.max(Max - Min, (Sum + M - 1 ) / M)); } } |
C#
using System; using System.Linq; public class GFG { // Driver Function public static void Main( string [] args) { // Inputs int N = 3; long M = 2; long [] arr = { 1, 2, 3 }; // Function call MinOperations(N, M, arr); } // Method to output the minimum number of operations // required public static void MinOperations( int N, long M, long [] arr) { // Variable storing max element of arr long Max = arr.Max(); // Variable to store the sum of differences long Sum = 0; // Variable storing min element of arr long Min = arr.Min(); // Calculating sum of differences with max element foreach ( var num in arr) { Sum += (Max - num); } // Printing the required minimum operations Console.WriteLine( Math.Max(Max - Min, (Sum + M - 1) / M)); } } |
Javascript
// Function to find the minimum number of operations required function MinOperations(N, M, arr) { // Finding the maximum and minimum elements in the array let Max = Math.max(...arr); let Min = Math.min(...arr); // Calculating the sum of differences with the maximum element let Sum = arr.reduce((acc, curr) => acc + (Max - curr), 0); // Printing the required minimum operations console.log(Math.max(Max - Min, Math.ceil(Sum / M))); } // Driver code function main() { // Inputs let N = 3; let M = 2; let arr = [1, 2, 3]; // Function call MinOperations(N, M, arr); } // Invoke main function main(); |
Python3
# Python Implementation # Function to output the minimum number of operations required def min_operations(N, M, arr): # Variable storing max element of A[] Max = max (arr) # Variable to store the sum of differences Sum = 0 # Variable storing min element of A[] Min = min (arr) # Calculating sum of differences with max element for i in range (N): Sum + = ( Max - arr[i]) # Printing the required minimum operations print ( max ( Max - Min , ( Sum + M - 1 ) / / M)) # Driver Function if __name__ = = "__main__" : # Inputs N = 3 M = 2 arr = [ 1 , 2 , 3 ] # Function call min_operations(N, M, arr) # This code is contributed by Tapesh(tapeshdu420) |
2
Time Complexity: O(N), where N is the size of input array arr[].
Auxiliary Space: O(1)
Contact Us