# Count minimum steps to get the given array

0
273

## 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.

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

Next articleFind the lost element from a duplicated array
If you have come this far, it means that you liked what you are reading. I am a software developer (graduated from BITS Pilani). I love writing technical articles on programming and data structures.