Wristband freebies
MediumOnline Assessment
Tally how many freebies each festival wristband earns across a row of stalls.
A festival hands out wristbands numbered 1 to total. Along the midway are several stalls, one per entry of intervals. Every wristband visits every stall once. A stall with interval k gives a freebie to a visiting wristband whose number is a multiple of k, so a wristband earns one freebie from each stall whose interval divides its number. Two stalls may have the same interval; they are still two separate stalls, each giving its own freebie.
Sort the wristbands by how many freebies they earned in total.
Input: total, the number of wristbands; intervals, the list of stall intervals.
Output: a list [none, odd, even] where none is the number of wristbands that earned no freebie, odd is the number that earned an odd number of freebies, and even is the number that earned an even number of freebies that is at least 2. The three values always add up to total.
total can be as large as a trillion, so handing out wristbands one at a time will not finish in time.
Example 1
- Input:
- [30,[2,3]]
- Output:
- [10,15,5]
- Explanation
- Stall 2 serves 15 wristbands and stall 3 serves 10; the 5 multiples of 6 are served by both. So 10 + 5 = 15 wristbands get exactly one freebie, 5 get two (an even, positive number), and 30 - 15 - 10 + 5 = 10 get none.
Example 2
- Input:
- [24,[4,4,6]]
- Output:
- [16,4,4]
- Explanation
- Two stalls share the interval 4, so every multiple of 4 gets two freebies from them. The numbers 4, 8, 16, 20 get 2 (even). The numbers 12 and 24 are also multiples of 6, so they get 3 (odd). The numbers 6 and 18 get 1 (odd). Everyone else, 16 wristbands, gets none: the result is
[16, 4, 4].
Example 3
- Input:
- [10,[1,5]]
- Output:
- [0,8,2]
- Explanation
- Interval 1 means every wristband is served by that stall. The multiples of 5 (5 and 10) are served by the second stall too, so they get 2 freebies. The other 8 get exactly 1. Nobody gets none.
Constraints
0 <= total <= 1,000,000,000,0001 <= intervals.length <= 141 <= intervals[i] <= 1,000,000,000,000; values may repeat- the three counts in the output all fit in a 64-bit integer