Count minimum steps to get the given desired array

Problem Statement

Suppose you have an array containing only integer 0 as all of its elements. Consider, you are given an array of length n having all 0s in which we have to convert the 0s to the given required array. We can name the required array as the desiredArr array. Thus we need to count minimum steps to get the given desired array. That is to find out the minimum number of possible operations need to change the zero array to the given required array. We can do the following operations only.

1. Doubling operation: Either we can double the element value of an array, or
2. Incremental operations: We can increment the element of the array’s value by 1.

Example

desiredArr[] = {1, 2}

3

Explanation:

Convert {0,0} to desired array

• Increase both of the element’s value by 1 → (2 operations)
• Increase the second element by 1→ (1 more operation)
• That makes it a total of 3 operations.

desiredArr[] = {4, 2}

4

Explanation:

• Increase both of the element’s values by 1 → (2 operations)
• Double all the array elements’ value → (1 operation)
• Double the first element → (1 more operation)
• That makes it a total of 4 operations.

Algorithm to count minimum steps to get the given desired array

1. Get the desiredArr array.
2. Set output as 0.
3. Check if all the elements given are even, then divide all the elements by 2 and increase the output by 1.
4. Get all of the odd elements, make them even by decrease their value by 1.
5. For every decrement, increase the value of output by 1.
6. We get all zeros in desiredArr array, after completing all the steps.
7. Return output.

Explanation

We have given the input array and also suppose we have the array which just contains the element 0 only, on which we want to perform an operation to count minimum steps to get the given desired array. Performed operations should satisfy the given instructions. That means we create the required array only performing operations satisfying given instructions.

The first operation is we can increase the array’s element value by 1. This counts in n operations, it means that if we are increasing n number of element’s value by 1. The second operation is to double the whole array, not an element but to multiply the whole array by 2. So if we multiply the whole array by 2 we can get the 1 operation is done. So, if we count the number of operations in incrementing both of the value by 1 and then double the array once, this means we have the total number of operations as 3.

We can take the example as arr[]={4, 2}, and also we need to assume that we have an array of 0s. So first we have to increase the value of elements by 1, so we count 2 operations. Now we have {1, 1} as an array. Now we double the whole array so we get {2, 2} and 3 operations total. We just need to have 4 in the first position. So for that, we double that value and till now we have done 4 operations in total. 4 is our minimum step count to get the desired array.

This was just an intuitive way of understanding. But instead of doing this, we are going to convert the input array into an array of 0s. So, for doing this we perform opposite to that of given operations. We decrement elements if they are odd, and once we have all the elements of the array even. We divide each of them(elements in the array) by 2 and this counts as a single operation. Like for example [4,2] -> [2,1] -> [2,0] -> [1,0] -> [0,0] gets though the changes as shown.

Note

This technique is used in other problems as well. Conversion of an integer A to B using similar instructions is one of them. We can either decrement A by 1 or multiply A by 2. Once again we try to convert B to A, that is much easier as compared to other solution for the proposed problem.

Code to count minimum steps to get the given desired array

C++ Code

#include<iostream>
using namespace std;

int getMinimumOperations(unsigned int desiredArr[], int n)
{
    int output = 0;
    while (1)
    {
        int zeroArrCnt= 0;

        int i;
        for (i=0; i<n; i++)
        {
            if (desiredArr[i] & 1)
                break;

            else if (desiredArr[i] == 0)
                zeroArrCnt++;
        }
        if (zeroArrCnt== n)
            return output;
        if (i == n)
        {
            for (int j=0; j<n; j++)
                desiredArr[j] = desiredArr[j]/2;
            output++;
        }
        for (int j=i; j<n; j++)
        {
            if (desiredArr[j] & 1)
            {
                desiredArr[j]--;
                output++;
            }
        }
    }
}
int main()
{
    unsigned int arr[] = {4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout <<getMinimumOperations(arr, n);
    return 0;
}

4

Java Code

class minimumSteps
{
    public static int getMinimumOperations(int arr[],int n)
    {
        int output = 0;
        while (true)
        {

            int zeroArrCnt= 0;

            int i;
            for (i=0; i<n; i++)
            {
                if (arr[i] % 2 == 1)
                    break;
                else if (arr[i] == 0)
                    zeroArrCnt++;
            }
            if (zeroArrCnt== n)
                return output;

            if (i == n)
            {
                for (int j=0; j<n; j++)
                    arr[j] = arr[j]/2;
                output++;
            }
            for (int j=i; j<n; j++)
            {
                if (arr[j] %2 == 1)
                {
                    arr[j]--;
                    output++;
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {4, 2} ;
        System.out.println(getMinimumOperations(arr,arr.length));
    }
}

4

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.