Bulb Challenge in Javascript

Let's start with an example: You are given 4 light bulbs at positions 0, 1, 2, 3; the second light bulb is switched on:

[0, 1, 0, 0]

You then iterate through the light bulbs from 0 to 3 and whenever you encounter a switched-off light bulb, you turn it on and you invert all switches to the right.

[1, 0, 1, 1] // Bulb 0 is switched on, bulb 1, 2 and 3 inverted
 ^

[1, 1, 0, 0] // Bulb 1 is switched on, bulb 2 and 3 inverted
    ^

[1, 1, 1, 1] // Bulb 2 is switched on, bulb 3 inverted
       ^ 

[1, 1, 1, 1] // Bulb 3 is on, do nothing
          ^

You needed to press three switches to turn all light bulbs on.

Let's now encode the above schema into a JavaScript function:

function bulbs(arr) {
  var switched = 0;

  // Iterate through light bulbs from left to right:
  for (var i = 0; i < arr.length; i++) {
    var current = arr[i] === 1;               // True if bulb at position i is on
    if (current === false) {                  // It is off, so we press the switch
      switched++;
      for (var j = i; j < arr.length; j++) {  // Invert all bulbs to the right
        arr[j] = arr[j] === 1 ? 0 : 1;        // Invert 0 -> 1 and 1 -> 0
      }
    }
  }
  return switched;
}

This algorithm is correct, but it is slow. For each switch we press, we need to manually iterate through all bulbs on the right and invert them one by one. This algorithm has a worst-case runtime complexity of O(n²) where n is the number of light bulbs.

We can improve the performance by exploiting an important observation: The state of a light bulb at position i is predictably given by its initial state (on or off) and the number of times you pressed on any switch before reaching position i:

• If you pressed an even number of switches beforehand (0, 2, 4, ... times), its status equals its initial status.
• If you pressed an odd number of switches beforehand (1, 3, 5, ... times), its status equals the inverse of its initial status.

Now, you already store the number of switches you pressed in variable switched. In order to determine if switched is odd, you can use switched % 2 === 1. And if switched is odd, we have to invert the initial state of light bulb i to get its current state by performing !initial:

current = (switched % 2 === 1) ? !initial : initial;

This improved algorithm no longer features an inner for-loop and is therefore much faster with linear runtime complexity O(n).