Minimum operation to make all elements equal in Python
In this tutorial, we will learn about how to reduce the operation to make all elements equal in Python.
Take an array with the n positive integers number. we’d like a minimum number of operations to form all elements equally. we will add, multiply, subtract, or divide with any element in a component.
Problem
If the input array is = {1, 2, 3, 4} then we require a minimum of three operations to form all elements equally. for instance, we will make elements 4 by doing 3 additions.
Procedure
Select the element with the most frequency.
Now we’ve to try to n-x operations because there are x elements with an equivalent value.
Algo:
// Find the 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;
from collections import defaultdict def minOperation(arr, n): # Insert all elements in hash. Hash = defaultdict(lambda:0) for i in range(0, n): Hash[arr[i]] += 1 # find the max frequency max_count = 0 for i in Hash: if max_count < Hash[i]: max_count = Hash[i] # return result return n - max_count if __name__ == "__main__": arr = [1, 5, 2, 1, 3, 2, 1] n = len(arr) print(minOperation(arr, n)) # This code is contributed # by Rituraj Jain
Output:
4
An iterative method in O(n^2), sorting in O(N log N), and hashing in O(n) time complexity.
Also read: How to Construct an array from its pair-sum array in Python
Leave a Reply