# 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:

- Increment by 1: Increment one element at a time and every increment is a step towards desired array.
- 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

## Leave a Reply