|
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;
void MinOperations(int N, long M, long arr[]) {
long Max = *max_element(arr, arr + N);
long Sum = 0;
long Min = *min_element(arr, arr + N);
for (int i = 0; i < N; i++) {
Sum += (Max - arr[i]);
}
cout << max(Max - Min, (Sum + M - 1) / M) << endl;
}
int main() {
int N = 3;
long M = 2;
long arr[] = {1, 2, 3};
MinOperations(N, M, arr);
return 0;
}
|
Java
import java.util.*;
public class Main {
public static void main(String[] args)
{
int N = 3;
long M = 2;
long[] arr = { 1, 2, 3 };
MinOperations(N, M, arr);
}
public static void MinOperations(int N, long M,
long[] arr)
{
long Max = Arrays.stream(arr).max().getAsLong();
long Sum = 0;
long Min = Arrays.stream(arr).min().getAsLong();
for (int i = 0; i < N; i++) {
Sum += (Max - arr[i]);
}
System.out.println(Math.max(Max - Min, (Sum + M - 1) / M));
}
}
|
C#
using System;
using System.Linq;
public class GFG {
public static void Main(string[] args)
{
int N = 3;
long M = 2;
long[] arr = { 1, 2, 3 };
MinOperations(N, M, arr);
}
public static void MinOperations(int N, long M,
long[] arr)
{
long Max = arr.Max();
long Sum = 0;
long Min = arr.Min();
foreach(var num in arr) { Sum += (Max - num); }
Console.WriteLine(
Math.Max(Max - Min, (Sum + M - 1) / M));
}
}
|
Javascript
function MinOperations(N, M, arr) {
let Max = Math.max(...arr);
let Min = Math.min(...arr);
let Sum = arr.reduce((acc, curr) => acc + (Max - curr), 0);
console.log(Math.max(Max - Min, Math.ceil(Sum / M)));
}
function main() {
let N = 3;
let M = 2;
let arr = [1, 2, 3];
MinOperations(N, M, arr);
}
main();
|
Python3
def min_operations(N, M, arr):
Max = max(arr)
Sum = 0
Min = min(arr)
for i in range(N):
Sum += (Max - arr[i])
print(max(Max - Min, (Sum + M - 1) // M))
if __name__ == "__main__":
N = 3
M = 2
arr = [1, 2, 3]
min_operations(N, M, arr)
|
Time Complexity: O(N), where N is the size of input array arr[].
Auxiliary Space: O(1)
|
