Fixed Adjacent Values

See the original problem on HackerRank.

Given an array of integers where each element is obtained by adding either +1 or -1 to the previous element you need to find an element index with the minimum number of comparisons.

If the element is present multiple times then print the smallest index. If the element is not present print -1.

Input Format

int N, denoting the number of elements. int T, denoting the number of queries. N space separated elements, denoting the array to search. T lines, each containing the number to find.

Constraints

\( 10 \leq N \leq 10^6 \)
\( 1 \leq T \leq 100 \)
Each element fits the int32 representation.

Output Format

T lines, each containing the corresponding 0-based index of the searched element. The smallest if multiple elements with the same index exist. -1 if such element does not exist.

Sample Input

1
2
3
4
5
6


10 4
3 4 5 6 5 4 5 6 7 8
5
6
8
10

Sample Output 0

Solutions

C++ Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

int search(const vector<int>& v, int elem)
{
    int i = 0;
    while (i <= v.size()-1)
    {
        if (v[i] == elem)
            return i;

        i += abs(v[i]-elem);
    }
    return -1;
}

int main()
{
    int N, T, x;
    cin >> N >> T;
    vector<int> v(N);
    copy_n(istream_iterator<int>(cin), N, begin(v));
    while (T--)
    {
        cin >> x;
        cout << search(v, x) << endl;
    }
}

A C++ solution that preprocesses the array to query in O(1) time (idea of Domenico N. and Andrea G.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N, T;
    cin >> N >> T;
    vector<int> leftmost_indexes(2*N + 1, -1);
    int baseline;
    cin >> baseline;
    leftmost_indexes[N] = 0;

    for (int idx = 1; idx < N; ++idx) {
        int n;
        cin >> n;
        if (leftmost_indexes[N + (n - baseline)] == -1)
            leftmost_indexes[N + (n - baseline)] = idx;
    }

    while (T--) {
        int q;
        cin >> q;
        int offset = q - baseline;
        cout << (abs(offset) > N ? -1 : leftmost_indexes[N + offset]) << "\n";
    }
}

ad hoc