Given an array of size n containing 0's and 1's and two operations, find the minimum number of operations to make all elements as 0

1
votes

Given an array of size n containing 0's and 1's and two operations, find the minimum number of operations to make all elements as 0.

Operations :

  1. Flip the ith element if the (i+1)th element is 1 and from (i+2)th to all consecutive elements are 0 or does not exist(if i+2 = n). (0 <= i <= n-2)

    For example, the above operation is applicable for :

on this element

|

V

1100

or

on this element

  |

  V

1011

  1. Flip the nth element without any restriction.

n <= 50

For example Input: 1,0,0,0

Output: 15

Explanation:

1000 -> 1001 -> 1011 -> 1010 -> 1110 -> 1111 -> 1101 -> 1100 -> 0100 -> 0101 -> 0111 -> 0110 -> 0010 -> 0011 -> 0001 -> 0000

1
algorithmbit-manipulation
Why can't you just flip the first 1 to 0(2nd rule, without any restriction)? It takes only one operation – Andrew Scott
@AndrewScott the 2nd rule applies only on the last bit (nth). To OP: what is the limit for n? – Georgi Gerganov
@user3386109 true. OP should clarify the problem statement – Georgi Gerganov
@GeorgiGerganov Sorry, I withdrew my comment because it occurred to me that there is an nth element, but there is no element at index n. I agree that OP should clarify the problem statement. – user3386109
@Dharsam1990 Please also add the limit for n and also running time limitations if there's any. – jal

1 Answers

4
votes

On any array other than the ones with all 0s only two operations are possible. Either flip the nth element or flip the element right before the last 1 in the array.
We don't need to consider the edge case of only the first element being 1 because we can add any number of zeros to the beginning of the array and it doesn't change the result, i.e. [1, 0, 0, 0] and [0, 1, 0, 0, 0] need the same amount of minimum operations to become all 0s.
This means that on every sequence of 0 and 1s one of the operations will go one step closer to 0s and the other operation goes one step further.
The result of these observations is that we actually have a numeric system much similar to binary and each operation can be seen as incrementing or decrementing a number by 1 and that means for every sequence of 0s and 1s there is an equivalent binary number and decimal number that is the number of steps between this number and 0.
I have found the relation between this system and binary which is like this:
If we iterate over the array from beginning to end and flip every element that comes after a 1 we get the equivalent binary. This operation needs to be done in place, meaning we mutate the array itself as we iterate and the result of each iteration affects the next iteration. I don't have a proof on why this is correct, maybe someone can provide a proof.

With all that said the algorithm itself is simple. This is in python:

a = [1, 0, 0, 0]

# convert to equivalent binary
for i in range(1, len(a)):
    a[i] = int(not a[i]) if a[i-1] == 1 else a[i]

# convert to decimal
bin_str = ''.join(map(str, a))
print(int(bin_str, 2))