Minimum Steps

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
6 upvotes
Asked in companies
MicrosoftWells FargoOracle

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
3
5 2 3
4
1 2 1 1
Sample Output 1:
3
1
Explanation:
For the first test case, ‘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.

For the second test case, arr = [1 2 1 1], 

In the first step, you can change 2 to 1, so the new array is [1, 1, 1, 1].

Hence the answer is 1.
Sample Input 2:
2
3
2 2 2
4
1 1 2 2
Sample Output 2:
0   
2
Hint

Try to think of a brute force approach.

Approaches (2)
Brute Force

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.
Time Complexity

O(N^3), Where N is the number of elements in the array.

 

We are iterating over the array until all the elements become equal. In the worst case, this will take O(N^2) time, and each element will be changed N times to become equal. Hence the overall time complexity will be O(N^3).

Space Complexity

O(1).
 

There is no extra space taken. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Minimum Steps
Full screen
Console