All problems

Lamp Panel

Medium · bit manipulation

A control panel has up to 16 lamps in a row, numbered from 0. The state of the whole row is written as one integer: bit i is 1 when lamp i is on and 0 when it is off.

You are given the current state start, the wanted state target, and a list switches. Each switch is also an integer in the same form: pressing it flips every lamp whose bit is 1 in that integer (a lamp that was on goes off, a lamp that was off comes on). You may press any switch any number of times, in any order.

Return the smallest number of presses that turns start into target. If start already equals target, return 0. If the target can never be reached, return -1.

Examples

Example 1

Input: start = 5, target = 0, switches = [1, 4, 6]

Output: 2

5 is 101 in binary (lamps 0 and 2 on). Pressing 1 switches off lamp 0 and pressing 4 switches off lamp 2, so two presses are enough.

Example 2

Input: start = 3, target = 12, switches = [1, 2, 4, 8]

Output: 4

Every lamp has to change, and each switch changes one lamp, so all four switches are pressed.

Example 3

Input: start = 0, target = 1, switches = [2, 4]

Output: -1

Neither switch touches lamp 0, so it can never come on.

Constraints