We are given an array consisting of n elements. At each operation you can select any one element and increase rest of n-1 elements by 1. You have to make all elements equal performing such operation as many times you wish. Find the minimum number of operations needed for this.
Examples:
Input : arr[] = {1, 2, 3}
Output : Minimum Operation = 3
Explanation :
operation | increased elements | after increment
1 | 1, 2 | 2, 3, 3
2 | 1, 2 | 3, 4, 3
3 | 1, 3 | 4, 4, 4
Input : arr[] = {4, 3, 4}
Output : Minimum Operation = 2
Explanation :
operation | increased elements | after increment
1 | 1, 2 | 5, 4, 4
2 | 2, 3 | 5, 5, 5
Brute force : A simple way to make all elements equal is that at each step find the largest elements and then increase all rest n-1 elements by 1. We should keep doing this operation till all elements become equal. Time Complexity : O(n^2)
Better Approach : If we took a closer look at each operation as well problem statement we will find that increasing all n-1 element except the largest one is similar to decreasing the largest element only. So, the smallest elements need not to decrease any more and rest of elements will got decremented upto smallest one. In this way the total number of operation required for making all elements equal will be arraySum – n * (smallestElement). Time complexity will be same as that of finding smallest elements and array sum i.e. O(n).
// find array sum sum = arraySum (int arr[], int n); // find the smallest element from array small = smallest (int arr, int n); // calculate min operation required minOperation = sum - (n * small); // return result return minOperation;
Implementation:
C++
// CPP for finding minimum operation required #include <bits/stdc++.h> using namespace std; // function for finding array sum int arraySum(int arr[], int n) { int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; return sum; } // function for finding smallest element int smallest(int arr[], int n) { int small = INT_MAX; for (int i = 0; i < n; i++) if (arr[i] < small) small = arr[i]; return small; } // function for finding min operation int minOp(int arr[], int n) { // find array sum int sum = arraySum(arr, n); // find the smallest element from array int small = smallest(arr, n); // calculate min operation required int minOperation = sum - (n * small); // return result return minOperation; } // driver function int main() { int arr[] = { 5, 6, 2, 4, 3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Minimum Operation = " << minOp(arr, n); return 0; } // This code is contributed by Sania Kumari Gupta |
C++
// [STL] - CPP for finding minimum operation required #include<bits/stdc++.h> using namespace std; // function for finding min operation int minOp (int arr[], int n) { // find array sum int sum = accumulate(arr,arr+n,0); // find the smallest element from array int small = *min_element(arr,arr+n); // calculate min operation required int minOperation = sum - (n * small); // return result return minOperation; } //driver function int main() { int arr[] = {5, 6, 2, 4, 3}; int n = sizeof(arr)/ sizeof(arr[0]); cout << "Minimum Operation = " << minOp (arr, n); return 0; } // This code is contributed by Sania Kumari Gupta |
C
// C for finding minimum operation required #include <limits.h> #include <stdio.h> // function for finding array sum int arraySum(int arr[], int n) { int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; return sum; } // function for finding smallest element int smallest(int arr[], int n) { int small = INT_MAX; for (int i = 0; i < n; i++) if (arr[i] < small) small = arr[i]; return small; } // function for finding min operation int minOp(int arr[], int n) { // find array sum int sum = arraySum(arr, n); // find the smallest element from array int small = smallest(arr, n); // calculate min operation required int minOperation = sum - (n * small); // return result return minOperation; } // driver function int main() { int arr[] = { 5, 6, 2, 4, 3 }; int n = sizeof(arr) / sizeof(arr[0]); printf("Minimum Operation = %d", minOp(arr, n)); return 0; } // This code is contributed by Sania Kumari Gupta |
Java
// Java program to find min operation import java.io.*; class minOperation { // Function to print minimum operation required to make // all elements of an array equal static void printMinOp(int arr[]) { int arraySum, smallest, arr_size = arr.length; arraySum = 0; smallest = arr[0]; for (int i = 0; i < arr_size; i++) { // If current element is smaller than update smallest if (arr[i] < smallest) smallest = arr[i]; // find array sum arraySum += arr[i]; } int minOperation = arraySum - arr_size * smallest; // Print min operation required System.out.println("Minimum Operation = " + minOperation); } // Driver program to test above functions public static void main(String[] args) { int arr[] = { 5, 6, 2, 4, 3 }; printMinOp(arr); } } // This code is contributed by Sania Kumari Gupta |
Python3
# Python 3 for finding minimum # operation required # function for finding min # operation def minOp (arr, n) : # find array sum sm = sum(arr) # find the smallest element from # array small = min(arr) # calculate min operation required minOperation = sm - (n * small) # return result return minOperation # Driver function arr = [5, 6, 2, 4, 3] n = len(arr) print( "Minimum Operation = ", minOp (arr, n)) # This code is contributed by Shubham Singh |
C#
// C# program to find min operation using System; class GFG { /* Function to print minimum operation required to make all elements of an array equal */ static void printMinOp(int []arr) { int arraySum, smallest, arr_size = arr.Length; arraySum = 0; smallest = arr[0]; for (int i = 0; i < arr_size ; i ++) { /* If current element is smaller than update smallest */ if (arr[i] < smallest) smallest = arr[i]; /*find array sum */ arraySum += arr[i]; } int minOperation = arraySum - arr_size * smallest; /* Print min operation required */ Console.Write("Minimum Operation = " + minOperation); } /* Driver program to test above functions */ public static void Main () { int []arr = {5, 6, 2, 4, 3}; printMinOp(arr); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP for finding minimum operation required // function for finding array sum function arraySum ($arr, $n) { $sum = 0; for ($i = 0; $i < $n; $sum += $arr[$i++]); return $sum; } // function for finding smallest element function smallest ($arr, $n) { $small = PHP_INT_MAX; for ($i = 0; $i < $n; $i++) if ($arr[$i] < $small) $small = $arr[$i]; return $small; } // function for finding min operation function minOp ($arr, $n) { // find array sum $sum = arraySum ($arr, $n); // find the smallest // element from array $small = smallest ($arr, $n); // calculate min operation // required $minOperation = $sum - ($n * $small); // return result return $minOperation; } // Driver Code $arr = array (5, 6, 2, 4, 3); $n = sizeof($arr); echo "Minimum Operation = " , minOp ($arr, $n); // This code is contributed by m_kit ?> |
Javascript
<script> // javascript program to find min operationclass minOeration{ /* * Function to print minimum operation required to make all elements of an array * equal */ function printMinOp(arr) { var arraySum, smallest, arr_size = arr.length; arraySum = 0; smallest = arr[0]; for (i = 0; i < arr_size; i++) { /* * If current element is smaller than update smallest */ if (arr[i] < smallest) smallest = arr[i]; /* find array sum */ arraySum += arr[i]; } var minOperation = arraySum - arr_size * smallest; /* Print min operation required */ document.write("Minimum Operation = " + minOperation); } /* Driver program to test above functions */ var arr = [ 5, 6, 2, 4, 3 ]; printMinOp(arr); // This code is contributed by aashish1995 </script> |
Output
Minimum Operation = 10
Time Complexity: O(N), where N represents the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
This article is contributed by Shivam Pradhan . If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
