[CHALLENGE] Find minimum steps to make an array zero

Events & Challenges
1

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.

2

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( [100] )
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= [100]
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
3

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

#include<stdio.h>
int main(){
	int i,j,a[10],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:[100]

Output:9

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

Output:2

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

Output:40
1 Like
4

Great job @mystic_devu! Plz reply to this thread with a link to your code on repl.it .

5

#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;
}

6

Here’s my solution for this challenge. All the code is documented :slight_smile: I’m not a native english speaker, so please be gentle :smiley:

You just have to type main() to launch it!