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

Posted in  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);

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

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
```