Bell tower rings
MediumOnline Assessment
Count the total number of times the bells of a tower ring over a long season.
A village has numbered bell ringers 1, 2, 3, .... Ringer number k rings the tower bell once on every day that is a multiple of k: days k, 2k, 3k, and so on, up to and including day days. A ringer never rings more than once in a day, and several ringers may ring on the same day; every ring counts separately.
Only ringers 1 through ringers are on the roster, so ringers with a higher number never ring. In addition, every ringer whose number is a multiple of holiday is on holiday for the entire season and does not ring at all. With holiday = 1 every ringer is on holiday.
Input:
days: the number of days in the season.ringers: the number of ringers on the roster.holiday: the holiday divisor.
Output: an integer, the total number of rings during days 1 through days.
The season can last up to ten billion days, so you cannot loop over the ringers one at a time.
Example 1
- Input:
- [10,4,2]
- Output:
- 13
- Explanation
- Ringers 1 to 4 are on the roster and ringers 2 and 4 are on holiday. Ringer 1 rings on all 10 days and ringer 3 rings on days 3, 6 and 9, giving 10 + 3 = 13.
Example 2
- Input:
- [20,20,3]
- Output:
- 52
- Explanation
- All 20 ringers are on the roster. Without holidays the rings are 20, 10, 6, 5, 4, 3, 2, 2, 2, 2 for ringers 1 to 10 and 1 each for ringers 11 to 20, which is 66. Ringers 3, 6, 9, 12, 15 and 18 are on holiday and would have rung 6, 3, 2, 1, 1 and 1 times, so 66 minus 14 is 52.
Example 3
- Input:
- [5,100,7]
- Output:
- 10
- Explanation
- The roster is far longer than the season, but ringers numbered above 5 never get a ring in because their first day is beyond day 5. The holiday divisor 7 is larger than every useful ringer number, so nobody is on holiday: 5 + 2 + 1 + 1 + 1 = 10.
Constraints
1 <= days <= 10,000,000,0001 <= ringers <= 10,000,000,0001 <= holiday <= 10,000,000,000- the answer fits in a 64-bit integer