Reach a desired array in minimum steps with limited operations in Python

In this tutorial, we are going to start with a zero array (that is an array/list of all zeros) and arrive at a desired array in Python by using a combination of two operations of either doubling the entire array or by incrementing one element at a time.

Operations:

1. Increment by 1: Increment one element at a time and every increment is a step towards desired array.
2. Double the array: Doubling the entire array/list and every doubling operation is a step towards desired array.

Reverse approach to determine array operations in Python

In order to determine the minimum number of operations required to arrive at the desired array let us begin with the desired array and trace our steps backward towards a zero array to determine the necessary operations.

Approach:

Decrement all odd elements of the array by one to reach an even array or make the respective element 0.

If the whole array is even then divide all the elements of the array by 2.

Keep track of all operations (operation sequence element wise).

Retrace the operations to start with a zero array and reach the desired array in minimum number of steps.

Code:

# using reverse approach to find the minimum number of operations required


def array_tracing(array_desired: list):
    array_length = len(array_desired)   # length of the desired array
    opcode_sequence = []   # empty list to keep track of the operations sequence
    while True:
        zero_count = 0   # reseting the number of zeroes count in the array after each iteration
        i = 0
        while i < length_of_array:
            if (int(array_desired[i]) & 1) > 0:   # checking for the index of first odd number in the sequence
                break
            elif array_desired[i] == 0:   # to keep track of number of zeroes in the array
                zero_count += 1
            i += 1

        if zero_count == array_length:   # if the whole array is zero then we have determined the operation sequence
            return opcode_sequence

        elif i == array_length:   # if there is no odd number in the array then entire array is even
            for j in range(array_length):
                array_desired[j] /= 2   # since entire array is even we did the entire array
            opcode_sequence.append(("double array", 0))   # updating opcode sequence with doubling operation

        for j in range(i, array_length):  # decrementing all the odd numbers in the array starting with the first odd number
            if int(array_desired[j]) & 1:
                array_desired[j] = array_desired[j] - 1
                # updating the opcode sequence with increment operation and the index of the number undergoing the operation
                opcode_sequence.append(("increment by 1", j))

# user input of the desired array
desired_array = list(map(int, input('Enter the elements of the desired array with elements separated by space:\n').strip().split()))
length_of_array = len(desired_array)
print(desired_array)
# initial zero array to perform the operations dictated by the opcode sequence
final_array = [0] * length_of_array

ops = array_tracing(desired_array)
# reversing the operation sequence since the tracing was backwards
ops.reverse()

#  print(ops)
steps = len(ops)   # minimum number of steps to reach the desired array is the length of the opcode sequence
print(f'Minimum steps to obtain desired array: {steps}\n')
print("Individual steps:\n")
for item in ops:
    if item[0] == "double array":
        for j in range(length_of_array):
            final_array[j] = final_array[j] * 2
        print(final_array)
    if item[0] == "increment by 1":
        i = item[1]
        final_array[i] = final_array[i] + 1
        print(final_array)

Output:

Enter the elements of the desired array with elements separated by space:
4 5 4
[4, 5, 4]
Minimum steps to obtain desired array: 6

Individual steps:

[0, 0, 1]
[0, 1, 1]
[1, 1, 1]
[2, 2, 2]
[4, 4, 4]
[4, 5, 4]

Also read: Find k numbers with most occurrences in the given Python array