PreviousOccurrence | Topcoder Archive

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.

Definition

Class:: PreviousOccurrence
Method:: findValue
Parameters:: int, int
Returns:: int
Method signature:: int findValue(int defaultValue, int query)
(be sure your method is public)

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.

Examples

```
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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.