Teaching Kids Programming – Flip to Zeros

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an integer list nums containing 0s and 1s. Consider an operation where we pick an index i in nums and flip i as well as all numbers to the right of i. Return the minimum number of operations required to make nums contain all 0s.

Constraints
n ≤ 100,000 where n is the length of nums.

Example 1
Input
nums = [1, 1, 0]
Output
2
Explanation
We can flip at index 0 to get [0, 0, 1] and then flip at index 2 to get [0, 0, 0]

Hint:
take a variable and check, where integer change from 0 to 1 and 1 to 0 and count

Min Number of Flips to Zeros

We can go from left to right, flipping each “One” to zero. As flipping any digit won’t affect the outcome on the left but the right digits will be affected. We need to remember the number of flips taken so far and use it to determine if the current digit is one or zero.

A digit flipped even number of times won’t change but odd number of flips will flip it.

So, we can determine the final value of a digit and decide if we should flip it.

1
2
3
4
5
6
7

class Solution:
    def flipToZeros(self, nums):
        ans = 0
        for i in nums:
            if (i == 1 and ((ans & 1) == 0)) or (i == 0 and ((ans & 1) == 1)):
                ans += 1
        return ans

class Solution:
    def flipToZeros(self, nums):
        ans = 0
        for i in nums:
            if (i == 1 and ((ans & 1) == 0)) or (i == 0 and ((ans & 1) == 1)):
                ans += 1
        return ans

We can use XOR (exclusive or) to simplify the implementation:

1
2
3
4
5
6
7

class Solution:
    def flipToZeros(self, nums):
        ans = 0
        for i in nums:
            if i ^ (ans & 1) == 1:
                ans += 1
        return ans

class Solution:
    def flipToZeros(self, nums):
        ans = 0
        for i in nums:
            if i ^ (ans & 1) == 1:
                ans += 1
        return ans

Time complexity is O(N) and space complexity is O(1). N is the number of numbers in the nums.

–EOF (The Ultimate Computing & Technology Blog) —