n lamps numbered 1 to n is wired as a tree: lamp 1 is the root, and the parent of lamp v > 1 is lamp v // 2 (integer division). For example, lamp 1 has children 2 and 3, and lamp 3 has children 6 and 7.
All lamps start off. The switches in toggles are then applied in order: toggling x flips lamp x and every one of its descendants (lit lamps go dark, dark ones light up).
Return how many lamps are lit after all the toggles.n=6, toggles=[2, 1] → 3
Toggling 2 lights lamps 2, 4 and 5. Toggling 1 then flips all six: 2, 4 and 5 go dark while 1, 3 and 6 light up. Three lamps are on.
n=4, toggles=[3, 3, 4] → 1
Toggling 3 twice changes nothing. Toggling 4 lights only lamp 4, which has no descendants.
n=6, toggles=[2, 1]
3
Run checks the first 3 tests in your browser. Submit checks all 77 tests on the server, hidden ones included.