The group of switches is located in a horizontal row. The switch on the far right can be turned on or off at any time. Any other switch can only be toggled if the switch to the right of it is on and all other switches to the right are off. All switches are initially off. Create a function that takes n switches and returns the minimum number of switching needed to turn all switches on. It is necessary to output each step of switching the switches.

Example: 
n = 3;
[0; 0; 0] --> [0; 0; 1] --> [0; 1; 1] --> [0; 1; 0] --> [1; 1; 0] --> [1; 1; 1];
count = 5. 

My idea is to test the next switch we want to enable. Then check each switch to the right of it and check the required state. What solution can you suggest?

CodePudding user response：

This actually produces a Gray code sequence.

While you could certainly implement this in a quite naive way, we can also use the following observation: when we number the indexes in the array from right to left, starting with 0 for the rightmost entry, then the index at which a digit should toggle follows this sequence:

0 1 0 2 0 1 0 3 0 1 0 2 0...

When we number the outputs from 1 onward, then the above mentioned index corresponds to the index of the rightmost 1-bit in that number. This table should illustrate that point:

output numbering	in binary	index of rightmost 1	Gray code
1	00001	0	00001
2	00010	1	00011
3	00011	0	00010
4	00100	2	00110
5	00101	0	00111
6	00110	1	00101
7	00111	0	00100
8	01000	3	01100
9	01001	0	01101
10	01010	1	01111
...

If the input will not exceed 31 (light bulbs) we can use 32-bit manipulations to derive the index of the rightmost 1-bit. For instance i & ~(i - 1) returns the least significant bit of i that is set -- as a power of 2. To convert a power of 2 to a bit index we can use the little known Math.clz32 function.

We can keep track of how many bulbs are on and stop the loop when all are on (without actually counting bulbs from zero in each iteration):

function steps(bulbCount) {
    let i, onCount;
    const bulbs = Array(bulbCount).fill(0);
    console.log(...bulbs);
    
    for (i = 1, onCount = 0; onCount < bulbCount; i  ) {
        let index = bulbCount   Math.clz32(i & ~(i - 1)) - 32;
        bulbs[index] ^= 1; // Toggle
        onCount  = bulbs[index] || -1; // Either increment or decrement
        console.log(...bulbs);
    }

    return i - 1; // Number of switch actions
}

console.log("Number of switch operations: ", steps(4));

<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

For larger number of light bulbs you would need to replace the bit operators with a more "manual" implementation of the same principle, but there is hardly any practical use when you have to wait for over 2³¹ outputs to be generated...

Alternative

We could also use the following observation from Wikipedia:

the