Repeat Gap Sequence Term
MediumHash Map ยท Bloomberg
Return the nth term (1-indexed) of a sequence whose first term is 0.
Each later term looks at the term just before it, at position p. If that value also appeared at some earlier position, the new term is p - q, where q is the latest such earlier position. Otherwise the new term is 0.
Example 1
- Input:
- n = 10
- Output:
- 6
- Explanation
- The first nine terms are 0, 0, 1, 0, 2, 0, 2, 2, 1. The 1 in position 9 last appeared in position 3, so term 10 is 9 - 3 = 6.
Example 2
- Input:
- n = 16
- Output:
- 5
Example 3
- Input:
- n = 1
- Output:
- 0
Constraints
1 <= n <= 10^6- Every term is between
0andn - 1inclusive - Every term fits in a 32-bit integer