Last Updated: 29 Aug, 2021

Minimum Steps

Moderate

Asked in companies

Solve now

Problem statement

You are given an array ‘ARR’ consisting of ‘N’ integers. Your task is to make all the numbers equal. You decrease one of the largest numbers present in the array into a number that is just lower than the maximum number in one step.

For example:

You are given ‘ARR’ = [5, 2, 3]
In the first step, you can change 5 to 3, so the new array is [3, 2,3].

In the second step, you can change the 3 to 2, then the array is [2, 2,3].

In the third step, you can change the 3 to 2, then the array is [2, 2, 2] 

Hence the answer is 3.

Input Format:

 The first line of input contains the integer ‘T’ representing the number of test cases.

 The first line of each test case contains one integer ‘N’, representing the size of the array.

The second line of each test case contains ‘N’ space-separated strings representing the element of the array.

Output Format:

For each test case, print a single integer representing the number of steps it will take to make all the array elements equal.

Print a separate line for each test case.

Constraints:

1 <= T <= 10
1 <= N <= 10^6
1 <= ARR[i] <= 10^9

Time Limit: 1 sec

Note:

You do not need to print anything. It has already been taken care of. Just implement the function.

Solve now

Approaches

01 Approach

In this approach, we will find the largest and equal the second largest element in the array. Each time we do this, we will increase the number of steps by 1. We will repeat the process until all the elements are in the array are not equal.

We will create a function isEqual(arr). This function returns true if all the elements in arr are equal. Otherwise, it will return false.

Algorithm:

The function isEqual(arr):
- Set x equal to arr[0]
- Iterate num through arr
  - If num does not equal x
    - Return False
- Return True
Set steps as 0
While isEqual(arr) is not true
- Set maxElement equal to the minimum integer value
- Set maxIndex equal -1
- Set SecondMaxElement equal to minimum integer value
- Iterate index from 0 to n - 1
  - If arr[index] is greater than maxElement
    - Set secondMaxElement equal to maxElement
    - Set maxElement equal to arr[index]
    - Set maxIndex equal to index
  - Otherwise, if arr[index] is greater than secondMaxElement and arr[index] is not equal to maxElement then,
    - Set secondMaxElement as arr[index]
- Set arr[maxIndex] as secondMaxElement
- Increment steps steps by 1
Finally, return the variable steps.

Solve now

02 Approach

In this approach, we will sort the array in decreasing order. Then we will count all the number of elements that are the largest in the array and add that number in the total steps to take. We will iterate to the last position of the second largest element in the array, and we will continue.

Example:

4 4 3 3 3 3 2 2 2 1 1, For this step, we add 2 to the total number of stops.

3 3 3 3 3 3 2 2 2 1 1, For this step, we add 6 to the total no of steps.

2 2 2 2 2 2 2 2 2 1 1, For this step, we add 9 to the total no. of steps.

We don’t need to change the elements in the array. So every time we find an element that is smaller than the previous, we add its position to the total number of steps.

Algorithm:

If the size of arr is less than 2.
- Then return 0
Sort the array arr in descending order
Set steps as 0
Iterate index from 1 to the size of N -1
- If arr[index - 1] is less than arr[index]
  - Add index to steps
Finally, return the variable steps.

Solve now