Count minimum steps to get the given array

We are given a input array target[] containing n elements, we need to compute minimum number of operation from converting array[] of size n with all zeros to target[].

Operations

a)    Increment an element by 1 is one operation.
b)    Double all the elements is one operation.

Example

a)    Input: target array -> [1,1]

Output: 2,
Increment 1 for both elements in [0, 0] to get [1, 1]-> 2 operations.

b)    Input: target array -> [2, 2]

Output: 3,
Increment 1 for both elements in [0, 0] to get [1, 1] -> 2 operations,
Double all the elements in [1, 1] to get [2, 2] -> 1 operation
Total = 3

c)    Input: target array -> [2,3]

Output: 4,
Increment 1 for both elements in [0, 0] to get [1, 1] -> 2 operations,
Double all the elements in [1, 1] to get [2, 2] -> 1 operation
Increment 1 for second element in [2, 2] to get [2, 3] -> 1 operation,
Total = 4

d)    Input: target array -> [4, 4, 5]

Output: 6,
Increment 1 for all elements in [0, 0, 0] to get [1, 1, 1] -> 3 operations,
Double all the elements in [1, 1, 1] to get [2, 2, 2] -> 1 operation
Double all the elements in [2, 2, 2] to get [4, 4, 4] -> 1 operation
Increment 1 in 3rd element in [4, 4, 4] to get [4, 4, 5] -> 1 operation,
Total = 6

Algorithm

Basic idea : Count number of steps in converting the given array to zero array. This is same as converting zero array to target array

Step 1 : Create a function to find minimum number of operations.

Step 2 : Initialize minimum moves (min_moves)= 0

Step 3 : Count the number of zeroes in the array, if number of zeroes is equal to size of the array then return min_moves.

Step 4 : Traverse in the array to find odd numbers, if odd number found decrease the value by 1, increment min_moves by 1 and move forward until all the elements are even do this.

Step 5 : If all elements are even, divide all elements by 2 and increment min_moves only once by 1.

Step 6 : until all the elements in the array are zeroes continue this.

Step 7 : On the given input target array call this function, print it. It is the minimum number of steps.

Algorithm working

C++ Program

/* C++ program to count minimum number of operations
   to get the given target array */
#include <bits/stdc++.h>
using namespace std;
 
//we make the target array to zero array
//count the number of moves
//it is nothing but converting zero array into target array
int Minimum_Operations(unsigned int target[], int n)
{
    int min_moves = 0;
    //Till all elements become zero
    while(1)
    {
        //count of zeroes
        int zeroes = 0;
        int i;
        // i is index of first odd number
        for(i=0; i<n; i++)
        {
            if (target[i] & 1)// odd number
                {
                  break;
                }
            else if (target[i] == 0)//zeroes in target array
                {
                  zeroes++;
                }
        }
        //return moves when all the elements in target array are zero
        if (zeroes == n)
          {
            return min_moves;
          }
        //if i = n odd number is not found in the array
        // so all are even
        //Divide by two and increment 1 move
        if (i == n)
        {
            for (int j=0; j<n; j++)
            {
               target[j] = target[j]/2;
            }
            min_moves++;
        }
 
        //if odd number found decrese it by 1 
        // increment moves by 1
        for (int j=i; j<n; j++)
        {
           if (target[j] & 1)
           {
              target[j]--;
              min_moves++;
           }
        }
    }
}
 
//main function
int main()
{
    unsigned int arr[] = {4, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout <<"Minimum steps to get target array is: " << Minimum_Operations(arr, n);
    return 0;
}
Try It


Next > < Prev
Scroll to Top