Last Updated: 20 Jun, 2022

Count Minimum Steps

Moderate

Asked in company

Solve now

Problem statement

Ram is a bright student in his class. He is very good at mathematics. So to test his skills, one of his friends Shyam thought of giving him a task.

In the task, Shyam would give Ram a ‘TARGET’ array of ‘N’ length. And also give him an array ‘ARR’ of length ‘N’ with all zeros. Ram has to change the array ‘ARR’ into the ‘TARGET’ array using the minimum number of operations. The two types of operation that can be performed on the array ‘ARR’ are as follows:

1) Incremental operations: Choose 1 element from the array ‘ARR’ and increment its value by one.

2) Doubling operation: Double the values of all the elements of the array ‘ARR’.

Shyam is not as smart as Ram, He needs your assistance to find the minimum number of operations required to change the array ‘ARR’ into ‘TARGET’. So that he can verify the correctness of the answer given by Ram. Can you help him to find the minimum steps?.

We are given the desired array ‘TARGET’ containing ‘N’ elements. Compute and return the smallest possible number of the operations needed to change the array from all zeros to the desired array.

Example :

Input: ‘N’ = 2, ‘TARGET’ = {2, 3}

Output: 4
In this case, To get the target array from {0, 0}, we first, increment both elements by 1 (2 operations), then double the array (1 operation). Finally, increment the second element (1 more operation).

Input Format :

The first line will contain the integer 'T', the number of test cases.

Each test case consists of two lines.

The first line of input contains one integer, 'N', the length of the ‘TARGET’ array

Followed by a line containing space-separated ‘N’ non-negative integers, denoting the elements of the array.

Output format :

For each test case, print the minimum number of operations required to get the target array.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= 'N' <= 10^5
0 <= ‘TARGET[i]’ <= 10^9
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea for this approach is to try out every possible sequence of moves to get the ‘TARGET’ array. So at the start, we will have an array filled with zeros, and at each step, we will perform either operation one on any index or operation two on the whole array.

This can be done using recursion as there is a similar sub-problem involved. So the base case for our recursive solution will be to terminate when an index has its value greater than the value of the same index in the ‘TARGET’ array.

Algorithm:

// This Recursive function will try out every possible way to get the ‘TARGET’ array and return the minimum of all possibilities.

Int getMinimum(N, TARGET[], ARR[])

Initialize a variable named ‘allEqual’ with the value of ‘true’.
Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- If ‘ARR[i]>TARGET[i]’ return positive infinity.
- If ‘ARR[i] != TARGET[i]’
  - Assign ‘allEqual’ the value of ‘false’.
If ‘allEqual == true’ return 0
Initialize a variable named ‘minMoves’ with the value of positive infinity.
Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Increment the value of ‘ARR[i]’ by one.
- Initialize a variable named ‘currMoves’ with the value of ‘1 + getMinimum(N, TARGET, ARR)’.
- Assign ‘minMoves’ the minimum value of ‘minMoves’ and ‘currMoves’.
- Decrement the value of ‘ARR[i]’ by one.
Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Multiply ‘ARR[i]’ by 2.
Initialize a variable named ‘currMoves’ with the value of ‘1 + getMinimum(N, TARGET, ARR)’.
Assign ‘minMoves’ the minimum value of ‘minMoves’ and ‘currMoves’.
Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Divide ‘ARR[i]’ by 2.
Return ‘minMoves’.

// The function will return the minimum number of operations required to get the desired array.

Int minimumSteps(N, TARGET[])

Initialize an array ‘ARR’ of length ‘N’ with the initial value of zero.
Return ‘getMinimum(N, TARGET, ARR)’.

Solve now

02 Approach

The idea for this approach is to analyze the ‘TARGET’ array and apply the given operations in reverse order and find if we can make the ‘TARGET’ array equal to all zeros.

So the operations in reverse are now:

Decrement any index ‘i’ of the ‘TARGET’ array by one.
Divide all the elements of the ‘TARGET’ array by two.

So in our solution, we will first find out all odd elements, and if there are any we have to decrement them by one using first reverse operations, as it is not divisible by two and our array with all zeros can never have a state of real value as any of its element, then we divide the whole array by two as all of them are even, we can keep a variable to store the moves performed in a reverse manner and return that as our answer.

Algorithm:

// The function will return the minimum number of operations required to get the desired array.

Int minimumSteps(N, TARGET[])

Initialize a variable named ‘moves’ with the value of zero.
Initialize a variable named ‘allZero’ with the value of ‘false’
Run a while loop until ‘allZero == false’.
- Assign ‘allZero’ the value of ‘true’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’
  - If ‘TARGET[i]’ is odd
    - Decrement ‘TARGET[i]’ by one.
    - Increment ‘moves’ by one.
  - If ‘TARGET[i] != 0’
    - Assign ‘allZero’ the value of ‘false’.
- If ‘allZero == true’ skip this iteration.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’
  - Divide ‘TARGET[i]’ by two.
- Increment ‘moves’ by one.
Return ‘moves’.

Solve now