FastPrepPossible Timer Intervals with One Wrong Reading
Problems/Possible Timer Intervals with One Wrong Reading

Possible Timer Intervals with One Wrong Reading

Indeed logoIndeed● HardNEW GRADOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The author translated this test from an attached file: find every ring interval that fits a list of timer times, when the list may skip rings and may hold at most one wrong time, with the answers in increasing order.

The original prints how many intervals there are and then the intervals. Here you return the intervals in increasing order, so the count is the length of the list. The value limits and the three samples are the ones in the author's translation. The original allows up to 10^5 times. Here the limit is 5 * 10^4 so the tests can reach it.

The judged task matches the source at about 95%.

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^4
  • 1 <= times[i] <= 10^9
  • All values in times are different.

More Indeed problems

  • Insert into an Unrolled Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Course Completion OrderPHONE SCREEN · Seen May 2025
  • Recipes You Can PreparePHONE SCREEN · Seen May 2025
All Indeed interview questionsSee Indeed hiring insights
Saved
class Solution {
    public int[] possibleIntervals(int[] times) {
        // Write your code here.
    }
}
Checking account…