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

Problem

Given an array of integers, you need to find the minimum number of 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 a reverse manner. We first make all odd numbers even by decrementing them by 1. After this, we keep on dividing all the elements by 2 until all become zero.

For example, if the array is [16, 16, 16], then Since all elements are even, divide all of them by 2, the 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 is 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:

• Subarray with Sum k
• Find Maximum Subarray Sum
• Maximum Sum Circular Subarray
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Dutch National Flag Problem
• Construction of an Expression Tree
• Create a mirror of an m–ary Tree
• Find a Pair with the given sum in a BST
• Problems solved using partitioning logic of Quicksort
• In-place vs out-of-place algorithms