Find minimum moves required for converting a given array to an array of zeros

Posted in

Find minimum moves required for converting a given array to an array of zeros

Vinay Khatri
Last updated on June 29, 2022

    Problem

    Given an array of integers, you need to find the minimum number operations required for an array containing only zeros to get converted into this array by performing only two kinds of operations: 1: Increment any value by one 2: Double all elements of the array.

    Sample Input

    [16, 16, 16]

    Sample Output

    Operations are 7

    Approach

    Since we only need to find a minimum number of operations, we can perform the task in reverse manner. We first make all odd numbers as even by decrementing them by 1. After this, we keep on dividing all the elements by 2 until all becomes zero.  For example, if the array is [16, 16, 16], then Since all elements are even, divide all of them by 2, array becomes [8, 8, 8] After dividing by 2, array is [4, 4, 4] -> [2, 2, 2,] -.> [1, 1, 1] Now, since all elements are odd, decrement 1 from each.  The total number of operations are 7 in this case. The time complexity of this approach is O(Nlog(maximum element)).

    C Programming

    #include <stdio.h>
     
    int solve(int arr[], int n)
    {
    
        int ans = 0;
     
    
        while (1)
        {
            int zeros = 0;
     
    
            for (int i = 0; i < n; i++)
            {
    
                if (arr[i] % 2 == 1)
                {
                    --arr[i];
                    ++ans;
                }
                 if (arr[i] == 0) {
                    zeros++;
                }
            }
     
    
            if (zeros == n) {
                break;
            }
     
    
            for (int j = 0; j < n; j++) {
                arr[j] = arr[j] / 2;
            }
     
            ans++;
        }
     
    
        return ans;
    }
     
    int main(void)
    {
        int arr[] = { 16, 16, 16 };
        int n = sizeof(arr) / sizeof(arr[0]);
     
        printf("Operations are %d", solve(arr, n));
     
        return 0;
    }

    Output

    Operations are 7

    C++ Programming

    #include <bits/stdc++.h>
    using namespace std;
    int solve(int arr[], int n)
    {
    
        int ans = 0;
    
        while (1)
        {
            int zeros = 0;
     
            for (int i = 0; i < n; i++)
            {
    
                if (arr[i] % 2 == 1)
                {
                    --arr[i];
                    ++ans;
                }
                 if (arr[i] == 0) {
                    zeros++;
                }
            }
    
            if (zeros == n) {
                break;
            }
            for (int j = 0; j < n; j++) {
                arr[j] = arr[j] / 2;
            }
     
            ans++;
        } 
        return ans;
    }
     
    int main(void)
    {
        int arr[] = { 16, 16, 16 };
        int n = sizeof(arr) / sizeof(arr[0]);
     
        cout<<"Operations are "<<solve(arr, n);
     
        return 0;
    }

    Output

    Operations are 7

    Python Programming

    def solve(arr):
        ans = 0
    
        while True:
            zeros = 0
     
            for i in range(len(arr)):
    
                if arr[i] % 2 == 1:
                    arr[i] = arr[i] - 1
                    ans = ans + 1
     
    
                if arr[i] == 0:
                    zeros = zeros + 1
     
    
            if zeros == len(arr):
                break
     
    
            for j in range(len(arr)):
                arr[j] = arr[j] // 2
     
            ans = ans + 1
     
    
        return ans
     
    arr = [16, 16, 16]
    print("Operations are", solve(arr))

    Output

    Operations are 7
    

    People are also reading:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments