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
1
0
Returns: 0
1
1
Returns: 1
1
2
Returns: -1
1
47
Returns: -1
1
6387
Returns: -1
500
6839
Returns: 1459521
718
6211
Returns: 1437410
20
6793
Returns: 1431513
377
6659
Returns: 1394276
629
6819
Returns: 1382936
699
6267
Returns: 1342471
13
6872
Returns: 1339954
826
6905
Returns: 1330910
21
6371
Returns: 1293662
587
6475
Returns: 1291266
528
6262
Returns: 1281977
449
6830
Returns: 1261723
853
6712
Returns: 1251329
209
5655
Returns: 1239741
750
6965
Returns: 1238367
424
6823
Returns: 1236032
304
5810
Returns: 1222655
52
6694
Returns: 1217894
538
6332
Returns: 1216756
741
6327
Returns: 1216262
0
0
Returns: 0
0
2883
Returns: 43959
0
513
Returns: 2514
0
3525
Returns: 31610
0
4536
Returns: 61140
0
3717
Returns: 15245
586
0
Returns: 0
353
0
Returns: 0
265
0
Returns: 0
526
0
Returns: 0
397
0
Returns: 0
403
5043
Returns: 56702
43
6514
Returns: 83292
430
5396
Returns: 17096
26
840
Returns: 13979
2
2162
Returns: 26548
967
6491
Returns: 181087
495
5930
Returns: 144725
561
75
Returns: 649
941
6683
Returns: 243205
922
2586
Returns: 35763
583
3504
Returns: 66754
237
1948
Returns: 5353
537
4211
Returns: 52366
369
3623
Returns: 88724
982
1983
Returns: 41748
36
4596
Returns: 63175
385
5872
Returns: 93845
706
2896
Returns: 3329
617
2801
Returns: 22285
573
4712
Returns: 223446
782
1606
Returns: 10860
246
6461
Returns: 79801
862
5974
Returns: 55155
938
290
Returns: 2324
130
2736
Returns: 59538
102
2973
Returns: 38002
594
3143
Returns: 123142
522
4425
Returns: 62585
834
2072
Returns: 13525
101
5316
Returns: 113232
894
1860
Returns: 3002
951
5728
Returns: 12225
867
2744
Returns: 68737
225
3859
Returns: 15638
764
903
Returns: 12400
793
3414
Returns: 51316
621
2893
Returns: 104780
693
2346
Returns: 53574
902
6332
Returns: 27023
831
1958
Returns: 88885
1
1234
Returns: -1
1
5
Returns: -1
1
123
Returns: -1
1
6839
Returns: -1
242
5991
Returns: 1094550
1
3
Returns: -1
0
5410
Returns: 841337
1
6997
Returns: -1
1
4000
Returns: -1
0
1
Returns: 2