Bulbs | InterviewBit | Solution Explained

I explain the solution to the problem Bulbs in detail, along with visuals and code in Python3.

0. Bulbs: Problem Discussion

Given N bulbs, either on (1) or off (0).

Turning on ith bulb causes all remaining bulbs on the right to flip.

Find the min number of switches to turn all the bulbs on.

0.0. IO Format

  • input:
    • an array of binary values (representing bulb states)
  • output:
    • the minimum number of switches/flips/cost to turn all the values in the array to 1 (turn the bulbs on).
the simple logic to bulbs on interviewbit
the simple logic to bulbs on interviewbit

0.1. Examples

Take for example: [1,0,1].

  • the first value is 1, so we continue
  • the second value is 0, so
    • we increase the cost by 1
    • flip the remaining
    • the array becomes: [1,1,0]
  • the third value is now 0, so
    • we increase the cost by 1
    • flip the remaining (in this case there’s nothing on the right)
    • the array becomes: [1,1,1]
  • and thus we get the total cost of 2

1. Bulbs: Observations & Logic

1.0. Intuitions

Using the simple logic mentioned in the question itself, we can see how the simulation will run. It will take O(1) space, since we only store a single variable, and will take O(N*N) time, since we have to:

  • iterate over all the bits in the array: O(N)
  • for the 0 bits, flipping everything to the right is O(N) – and this is nested inside the above loop

So, how do we proceed to a solution?

1.1. An Interesting Example

Let’s take the case of [0,1,0,1,1,0,1,1]. The underline represents the current element we want to consider and the blue arrows represent the flipping (remember that each costs 1).

There’s something going on in the example, see if you can see it.

An interesting example
An interesting example
the observation needed to solve bulbs
the observation needed to solve bulbs

Notice the repetition when we align the two arrays!

This should not be all too surprising. Realize that when we flip and convert 1 to 0, we can flip again to convert 0 to 1. This means every two flips, we revert back to the original.

What’s the point of this though?

1.2. Mathematical Formulation

Here’s the simple mathematical representation of what’s happening.

  • for any bit b, and at the current cost, cost
  • we realize that if the cost is even, we have seen an even number of flips up till now
  • this means the bit b has reverted to its original state: b = b
  • else, if the cost is odd, we would invert the bit: b = !b
  • now, whatever the new b is, we check if its 1 or 0
  • if its 1, that means we can continue as before
  • else, we have to convert this 0 to a 1, and encounter the cost of 1
  • thus, we update the cost: cost = cost + 1 in this case
a formalization of the solution
a formalization of the solution

2. ProblemName: Optimized Implementation

2.0. Code

class Solution:
# @param A : list of integers
# @return an integer
def bulbs(self, A):
cost = 0 # O(1) space

for b in A: # O(N) time
if cost % 2 == 0: b = b
else: b = not b

if b % 2 == 1: continue
else: cost += 1

return cost

2.1. Complexity Analysis

  • Time: O(N), to iterate over all the bits in the array
  • Space: O(1), to store the cost variable

Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.


    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    4. Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

      A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

      Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

      To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

      Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

      This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

      Understanding why solar energy consultants assist clients via Matthew D’Agati.
      Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.