Minimum number of transformation steps required to make all elements of an array equal

   August 22, 2022

Problem definition

Given an array of N elements, our task is to find the minimum number of transformations that we can perform to make all the elements of the array equal.

Example

Input

1, 3, 4, 2

Output

3

Input

1, 3, 2, 3

Output

2

If we have arr = [1, 3, 4, 2], we will need to perform 3 transformations to make all the elements equal. Over here we can select any array element that we want to maintain. Let’s take 1 as the element, we will need to change 3, 4, and 2 with 1 so as to make it all equal.

Let’s now consider arr = [1, 3, 2, 3], if we now consider 1 as the element to be maintained, we will need to perform three transformations. 2, 3, and 3 will have to be replaced by 1. But, if we consider 3 as the element to be maintained, we will only need to perform 2 operations to replace 1 and 2 with 3. Thus, 2 is the minimum number of operations to be performed to make all elements equal.

Approach

We will need to maintain an element of the array and transform all the others. To get the best result we must maintain the element with the highest frequency.

So, we understand that we need to maintain the element with the highest frequency and transform all the other elements to get a minimum number of transformations. Thus, we can calculate the minimum number of transformations as the difference between the count of elements in the array and the maximum frequency.

Algorithm

1. initialize hashmap counter
2. find frequency of each element in array
3. find maximum frequency
4. return count of elements - maximum frequency

Code

def min_transformations(arr):
    n = len(arr)
    counter = {}

    for ele in arr:
        if ele in counter:
            counter[ele] += 1
        else:
            counter[ele] = 1

    max_freq = max(counter.values())
    return n - max_freq

min_t = min_transformations([1,3,3,4])
print(min_t)

Output

2

One line code

We can also write this code in a single line using python’s Counter function from the collections module

from collections import Counter

def min_transformations(arr):
    return len(arr) - max(Counter(arr).values())

print(min_transformations([2,1,3,2]))

Output

2

Let us know in the comment if you have any queries.

Also Read:

Share:

Author: Ayush Purawr