# [CHALLENGE] Find minimum steps to make an array zero

You have an array with N elements. Initially, each element is 0. You can perform the following operations
Increment operation : choose one element of the value by one.
Doubling operation : Double the value of each element

You are given a int desired array containing N elements. Compute and return the smallest possible number of operations needed to change the array from all zeros to desired array.

Sample Test Case 1 :
Input : {2,1}
Output : 3

One of the optimal solutions is to apply increment operations to element 0 twice and then to element 1 once. Total number of operations is 3.

Sample Test Case 2 :
Input : {16,16,16}
Output : 7

The optimal solution looks as follows First, apply as increment operation to each element. Then apply the doubling operation four time. Total number of operations is 3+4=7.

Sample Test Case 3 :
Input : {100}
Output : 9

Sample Test Case 4 :
Input : {0,0,1,0,1}
Output : 2

Some elements in desired Array may be zeros.

Sample Test Case 5 :
Input : {123,234,345,456,567,678}
Output : 40.

Okay, here is my submission in Python 3

My thoughts on algorithm choice are in the initial comments.

``````# determines the number of steps needed to
# go from an integer array of all zeroes
# to some desired integer array
# steps are either increment one element
# or double all elements
# I propose that one can go from the
# desired array to an array of zeroes
# in the same number of steps, by using
# the inverse operations of
# decrementing and halving
def how_many_steps( desired ):
print("desired=", desired)
steps= 0
# repeat until all elements are zero
while any(desired):
for n in range(len(desired)):
# check for any odd elements
# if there are any, decrement
if desired[n] % 2:
desired[n] -= 1
steps += 1 # count each one
# at this point we know that
# all elements are even, so
# it is safe to perform a halving
if any(desired): # any non-zero?
for n in range(len(desired)):
desired[n] //= 2
steps += 1 # count the halving
print("steps=", steps)
print()

how_many_steps( [2,1] )
how_many_steps( [16,16,16] )
how_many_steps(  )
how_many_steps( [0,0,1,0,1] )
how_many_steps( [ 123,234,345,456,567,678 ] )
``````

And here is the corresponding output:

``````desired= [2, 1]
steps= 3

desired= [16, 16, 16]
steps= 7

desired= 
steps= 9

desired= [0, 0, 1, 0, 1]
steps= 2

desired= [123, 234, 345, 456, 567, 678]
steps= 40
``````

Here is my repl.it link: https://repl.it/JgP3/25

3 Likes

I am a C programmer so here it is
Worked best in Dev C++ …

``````#include<stdio.h>
int main(){
int i,j,a,n,opr=0;
printf("******Sample Operations******\n");
printf("Enter number of Samples: ");
scanf("%d",&n);

for(i=0;i<n;i++){
printf("Enter number%d:",i+1);
scanf("%d",&a[i]);
}

printf("\n\nEntered	sample:["); //Listing input
for(i=0;i<n;i++){
printf("%d",a[i]);
if(i!=n-1){
printf(",");
}
}
printf("]\n\n");

for(i=0;i<n;i++){
while (a[i]!=0){      //loop till all numbers become zero
for(j=0;j<n;j++){
if(a[j]%2!=0){
a[j]-=1;   // search for odd numbers
opr++;
}
}
if(a[i]!=0){   //if not equal to zero
for(j=0;j<n;j++){
a[j]=a[j]/2; // divide by 2
}
opr++;
}
}
}

printf("Output:%d",opr); // output
return 0;
}
``````

And here is the corresponding output:
all outputs are merged

``````Entered sample:[1,2]

Output:3

Entered sample:[16, 16, 16]

Output:7

Entered sample:

Output:9

Entered sample:[0, 0, 1, 0, 1]

Output:2

Entered sample:[123, 234, 345, 456, 567, 678]

Output:40
``````
1 Like

#include
#include <conio.h>
using namespace std;
int main(){
int i=0,j=0,a=0,steps=0;
cout<<“Enter the Number of Elements of Array (N):”; //prompt of no of elements of array
cin>>a;
int *ptr1= new int [a]; //[0,0,0…N times]
int *ptr2= new int [a]; //Desired array
for( i=0 ; i< a ; i++){
ptr1[i]=0;
}
for( i=0 ; i<a ; i++){
cin>>ptr2[i];
}
cout<<“Input: {”;
for(i=0;i<a;i++){
cout<<ptr2[i];
if(i!=a-1){
cout<<",";
}
}
cout<<"}\n\n";
for( i=0 ; i<a ; i++){
while(ptr2[i]!=ptr1[i]){ //loop to become all element to zero
for(int k=0 ; k < a ; k++){
if(ptr2[k]%2!=ptr1[k]){
ptr2[k]-=1;
steps++;
}
}
if(ptr2[i]!=ptr1[i]){
for(int j=0 ; j< a ; j++){
ptr2[j]/=2;
}
steps++;
}
}
}
//computed steps
cout<<"Output: "<<steps;
}

Here’s my solution for this challenge. All the code is documented I’m not a native english speaker, so please be gentle You just have to type `main()` to launch it!