Count Minimum Steps

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in company
Nagarro Software

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 
2 1
3
4 4 4
Sample Output 1 :
3
5
Explanation Of Sample Input 1 :
For the first test case, One of the optimal solutions is to apply the incremental operation 2 times to the first and once on the second element.

Hence, the output will be: 3

For the second test case, The output solution looks as follows. First, apply an incremental operation to each element. Then apply the doubling operation two times. total number of operations is 3+2 = 5

Hence, the output will be: 5
Sample Input 2 :
2
5
0 0 0 1 2
4
0 1 1 3
Sample Output 2 :
3
5
Hint

Can we try out every possible sequence of moves?.

Approaches (2)
Brute Force

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

O((N+1)^(S)), Where ‘N’ is input integers, ‘TARGET’ is the input array, and S = Sum of all ‘TARGET[i]’.

The recurrence relation of the recursive solution is ‘T(S) = T(S-1) + T(S/2) + N’, where ‘S’ is the sum of all ‘TARGET[i]’ and ‘N’ is the length of the ‘TARGET’ array, hence the time complexity will be O((N+1)^(S))

Space Complexity

O(Sum of all TARGET[i]), Where ‘TARGET’ is the input array.

 

In the worst case, we have a recursion depth of ‘Sum of all TARGET[i]’, this happens in the case when we only apply the first operation, hence the space complexity will be O(Sum of all TARGET[i])

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