A community garden stores each plant's watering days as a 7-bit mask: bit d is set if the plant is watered on day d (0 = Monday, ..., 6 = Sunday). So 0b0000101 = 5 means Monday and Wednesday, and 0b1000000 = 64 means Sunday only.
Write two functions:
busiest_day(masks: list[int]) -> int: the day0..6on which the most plants are watered. On a tie, return the earliest day.disjoint_pairs(masks: list[int]) -> int: the number of pairs of plantsi < jthat share no watering day (masks[i] & masks[j] == 0). Such pairs can go to the same volunteer without ever clashing.
busiest_day([5, 1, 64]) # 0 (Monday: plants 0 and 1)
busiest_day([2, 4]) # 1 (tie between Tuesday and Wednesday: earliest wins)
disjoint_pairs([5, 1, 64]) # 2 (5 & 64 == 0 and 1 & 64 == 0, but 5 & 1 != 0)
disjoint_pairs([3, 3, 4, 4]) # 4 (each 3 pairs with each 4)
With 10^5 plants, checking every pair is about 5·10^9 checks, far too slow; disjoint_pairs must be close to linear in the number of plants.
Constraints: 1 <= len(masks) <= 10^5, 1 <= masks[i] <= 127 (every plant is watered at least once a week).
Show hint
test day d with (mask >> d) & 1. For the pairs, notice there are only 127 possible masks: group the plants by mask and compare mask values with each other instead of plants.