Lamp Toggles
Medium · rating 1450 · Prefix Sum
There are n lamps numbered 1..n, all off. The first line has n and m. Each of the next m lines has l r: toggle every lamp in [l, r]. Print how many lamps are on at the end.
Constraints: 1 ≤ n, m ≤ 105
Editorial
Approach
Toggling ranges is a difference-array job. For each toggle [l, r], add 1 at l and subtract 1 after r; a prefix sum then gives each lamp's total toggle count, and a lamp is on iff that count is odd.
for l, r in toggles: diff[l] += 1; diff[r+1] -= 1
cur = 0
for i in 1..n:
cur += diff[i]
if cur % 2: on += 1Complexity
Time: O(n + m). Space: O(n).
Related problems
- Product of Array Except Self — Hard
- Subarray With Target Sum — Medium
- Subarrays Divisible by K — Medium
- Subarrays Summing to K — Hard
- Prefix Sums — Easy