Minimum Switches to Turn On All Bulbs

Problem Given a set of switches and bulbs where each switch toggles a specific subset of bulbs, find the minimum number of switch presses needed to turn every bulb on. The exact switch-to-bulb mapping and toggle rules are clarified interactively with the interviewer, so part of the exercise is asking the right questions before writing code.

Input / Output

• Input: the number of bulbs n, their initial on/off state, and for each of the k switches the subset of bulbs it toggles.
• Output: the minimum number of switch presses that leaves all n bulbs on, or -1 if no combination achieves it.

Constraints

• Pressing a switch twice is the same as not pressing it, so only the subset of switches pressed matters — not the order, not repetition.
• k is small in the brute-force variant; structured variants (each switch toggles a contiguous range) allow much larger n.

Example

• 3 bulbs, all off; switch A toggles {1,2}, switch B toggles {2,3}, switch C toggles {1,2,3}.
• Pressing C alone turns all three on → answer 1; pressing A then B leaves bulb 2 off, since it is toggled twice.