Possible Timer Intervals with One Wrong Reading
Problem statement
A timer rings at a fixed interval. There is a start time s and a positive integer interval d, and the timer rings at times s, s + d, s + 2d, and so on.
You are given times, a list of recorded ring times in no particular order. The record has two problems:
- Not every ring was recorded.
- At most one recorded time is wrong: the timer did not ring at that time.
Return every interval d that is possible, in increasing order.
An interval d is possible if you can remove at most one time from times so that some start s makes every remaining time a ring time. Because the start can be any time, this means all remaining times leave the same remainder when divided by d.
Function
possibleIntervals(times: int[]) → int[]Examples
Example 1
times = [71,21,46,51,121]return = [1,2,5,10,25]If every time is correct, the interval must divide every gap, and the gaps from 21 are 25, 30, 50 and 100, so it must divide 5: that gives 1 and 5. If 46 is the wrong reading, the gaps among 21, 51, 71 and 121 are 30, 50 and 100, so 2 and 10 also work. If 51 is wrong, the gaps among 21, 46, 71 and 121 are 25, 50 and 100, so 25 works. Treating 21, 71 or 121 as wrong adds nothing new. The answer is [1,2,5,10,25].
Example 2
times = [27,28,26]return = [1,2]If 27 is the wrong reading, 26 and 28 are 2 apart, so the timer could ring every 1 or every 2 time units. Treating 26 or 28 as wrong leaves two times 1 apart, which only allows 1. The answer is [1,2].
Example 3
times = [3052864,514,204004,610984,516]return = [1,2,3,4,5,6,7,9,10,14,15,17,18,19,21,30,34,35,38,42,45,51,57,63,70,85,90,95,102,105,114,119,126,133,153,170,171,190,210,238,255,266,285,306,315,323,342,357,399,510,570,595,630,646,665,714,765,798,855,969,1071,1190,1197,1330,1530,1615,1710,1785,1938,1995,2142,2261,2394,2907,3230,3570,3990,4522,4845,5355,5814,5985,6783,9690,10710,11305,11970,13566,14535,20349,22610,29070,33915,40698,67830,101745,203490]514 and 516 are only 2 apart, so 2 is the only interval besides 1 that keeps both of them. If 514 or 516 is the wrong reading instead, the four other times must share one remainder, and many more intervals become possible. All 97 possible intervals are listed in increasing order.
Constraints
3 <= times.length <= 5 * 10^41 <= times[i] <= 10^9- All values in
timesare different.