← 返回 bloomberg 的题目列表Van Eck-like Sequence: N-th Term
类型：online_judge
Problem: Van Eck-like Sequence (n-th Term)
Given an integer n (n >= 1), define an integer sequence a as follows:
a[0] = 0
For i >= 1:
If a[i-1] has appeared before (i.e., there exists j with 0 <= j <= i-2 and a[j] == a[i-1]), let last_index be the most recent such index (the largest j). Then:
a[i] = (i - 1) - last_index
Otherwise:
a[i] = 0
Return the value of a[n-1].
Input Format
A single integer n.
Output Format
Print one integer: a[n-1].
Constraints (reasonable for interview)
1 <= n <= 200000 (overall complexity should be close to O(n))
Examples
Input:
1
Output:
0
Input:
4
Output:
0
Explanation:
a[0]=0
a[1]=0 (0 has not appeared before)
a[2]=1 (0 last appeared at index 0, so 1-0=1)
a[3]=0 (1 has not appeared before)
Additional example:
Input:
3
Output:
1
Example
Input
1
Output
0