Count Minimum Steps to Get the given Array

Problem Statement

In count minimum steps to get the given array problem, we have given an input array target[] containing n elements, we need to compute the minimum number of operations 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

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

2. Initialize minimum moves (min_moves)= 0

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

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

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

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

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

Implementation

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;
}

Minimum steps to get target array is: 6

import java.util.Scanner;
class sum
{
    //we make the target array to zero array
    //count the number of moves
    //it is nothing but converting zero array into target array
    public static int Minimum_Operations( int target[], int n)
    {
        int min_moves = 0;
        //Till all elements become zero
        while(1==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)== 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)==1)
               {
                  target[j]--;
                  min_moves++;
               }
            }
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("Minimum steps to get target array is: "+ Minimum_Operations(a,n)); 
    }
}

3
4 4 5

6