The zero array

We only need to iterate once through the list.

python3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def MinInc(n):         #Get the minimum increment for a given number
    inc = 0
    while n != 0:
        if n % 2 == 1:
            n -= 1
            inc += 1
        else: n //= 2
    return inc

def MinOpList(somelist):      #Finds the minimum number of operations done to the zero array
    from math import log         
    return sum(MinInc(e) for e in somelist) + int(log(max(somelist), 2))  

The number of doubling done to the list equals to the number of times we have doubled the maximum number of that list.

Very nice problem indeed. Very simple and thought provoking, I tried three approaches before realising that the correct approach is so simple and powerful. Thanks for this problem, please post more such problems.

For the solution:

The approach: In each pass(while loop), if each number is not divisible by 2, then decrement the number and increase operation count. Any number is then divisible by 2, so divide it by 2 and mark a boolean for updating operation count later. Once looped through all numbers, if the boolean for doubling operation was true, increment operation count. Keep making passes in a while loop until all of the numbers have been reduced to zero.

Here is the solution in C#. The 'list' object below is populated from input and cloned.

        int nOps = 0;
        List<int> clonedList = list.ToList();
        while (true)
        {
            bool doublingOpNeeded = false;
            for (int i = 0; i < clonedList.Count; i++)
            {
                if (clonedList[i] % 2 != 0) { clonedList[i]--; nOps++; }
                if (clonedList[i] > 0 && clonedList[i] % 2 == 0) { clonedList[i] /= 2; doublingOpNeeded = true; }
            }
            if (doublingOpNeeded) nOps++;

            if (clonedList.All(x => x == 0)) break;
        }

From leaf to root.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def preferred_operation(_array):
    return_array1=[]+_array
    return_array2=[]+_array
    for i in range(0,len(_array)):
        if _array[i]%2==1:
            return_array1[i]-=1
            return return_array1
        return_array2[i]=int(return_array2[i]/2)
    return return_array2

operations=0

target=[39, 26, 45, 20, 47, 35, 46, 37, 26, 34, 31, 29, 36, 21, 31, 47, 17, 49, 22, 28, 36, 40, 24, 24, 21, 43, 48, 31, 38, 27, 46, 19, 37, 39, 36, 19, 42, 37, 33, 24, 15, 22, 21, 34, 44, 27, 16, 30, 44, 45, 20, 21, 18, 24, 39, 44, 26, 30, 24, 33, 21, 32, 30, 29, 46, 39, 30, 25, 50, 17, 26, 33, 45, 44, 17, 29, 36, 17, 15, 50, 45, 21, 48, 45, 33, 18, 31, 18, 28, 37, 45, 16, 45, 30, 26, 21, 28, 37, 49, 36, 49, 48, 19, 46, 43, 23, 28, 19, 17, 35, 36, 30, 31, 49, 19, 30, 17, 48, 25, 19, 32, 45, 30, 25, 39, 47, 34, 38, 17, 17, 37, 17, 34, 27, 27, 44, 27, 47, 50, 49, 50, 26, 38, 38, 23, 46, 40, 15, 42]

while sum(target)!=0:
    operations+=1
    target=preferred_operation(target)

print(operations)