PreviousOccurrence
SRM 777 · 2020-01-26 · by misof
Problem Statement
A recursive sequence A is defined as follows: A[0] = 0, and for all n >= 0, A[n+1] is the distance between the last two occurrences of A[n], or defaultValue if the value A[n] doesn't have any previous occurrence.
For example, if defaultValue = 7, the sequence begins as follows: 0, 7, 7, 1, 7, 2, 7, 2, 2, 1, 6, 7, 5, 7, 2, 6, 5, ...
- A[0] = 0 is given.
- A[1] = 7 because the previous term (0) only occurs once.
- A[2] = 7 because the previous term (7) only occurs once.
- A[3] = 1 because the previous term (7) occurs at indices 2 and 1, and 2-1 = 1.
- A[4] = 7 because the previous term (1) only occurs once.
- A[5] = 2 because the last two occurrences of the previous term (7) are at indices 4 and 2, and 4-2 = 2.
- and so on
Find the index of the first occurrence of query. Return -1 if query never occurs in A.
Notes
- It is guaranteed that for the given constraints the correct return value always fits into a signed 32-bit integer.
Constraints
- defaultValue will be between 0 and 1000, inclusive.
- query will be between 0 and 7000, inclusive.
7 0 Returns: 0
We have the example sequence from the problem statement and we are looking for the first occurrence of the value 0. This value occurs at the very beginning.
7 2 Returns: 5
Same sequence. As we saw in the example, the first occurrence of the value 2 is at index 5.
7 47 Returns: 1261
Still the same sequence. The value 47 first occurs a bit farther into the sequence.
47 7 Returns: 66
47 6763 Returns: 540153
Submissions are judged against all 91 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PreviousOccurrence with a public method int findValue(int defaultValue, int query) · 91 test cases · 2 s / 256 MB per case