Impress the Interviewer

See the original problem on HackerRank.

Alan has finally reached the final round of interviews at Gugol. He is one step from catching the job he loves and he has to impress the interviewer with a killer answer to the last question.

The problem looks like very easy: given an array where all elements appear even number of times except one. All repeating occurrences of elements appear in pairs and these pairs are not adjacent (there cannot be more than two consecutive occurrences of any element). Find the element that appears odd number of times.

For example:

\({2, 2, 1, 2, 2, 1, 1}\) is a valid input, but \({1, 2, 2, 2, 2}\), \({2, 2, 2, 1}\) and \({2, 1, 2}\) are not.

Alan cannot give a naive answer to the question, though. He needs to design a solution that is better than linear and does not use extra memory!

Can you help Alan?

Please note that tests will pass with a linear solution too, but that’s not enough for Alan!

Input Format

The first line contains \(T\), the number of test cases.

For each test case you read:

• an integer \(N\)
• \(N\) numbers separated by whitespaces

Constraints

• \(1 \leq T \leq 10^3\)
• \(1 \leq N \leq 10^6\)
• Array numbers are 32bit integers

Output Format

Print the odd appearing element on a new line for each test-case.

Solutions

We call this kind of challenges “constrained”, meaning that we limit the admittable solutions space by applying some special constraints.

Generally, this means that the solution could be find more easily if we do not have such constraints.

In this case, we have a constraint on both time and space complexity (we want a linear-time and constant-space solution). In other examples we can “disable” some operations or using a certain input format, etc.

Some naive solutions

Scanning the array

Finding the odd occurrence by scanning the array (e.g. find the first element different from the previous and next ones)

1
2
3

search lst = c where
  triplets = zip3 lst (tail lst) (drop 2 lst)
  Just (_,c,_) = find (\(l,c,r) -> (c/=l) && (c/=r)) triplets

The previous approach could be generalized in case the domain changes by sorting the array (e.g. the input format changes)

XOR

Better than the previous and enough generic is using xor (see here)

1
2
3
4
5
6
7

int search(const std::vector<int>& arr) {
    int res = 0;
    for (int v: arr) {
        res ^= v;
    }
    return res;
}

A more functional approach using fold (called std::accumulate in C++)

1
2
3

int search(const std::vector<int>& arr) {
    return std::accumulate(arr.begin(), arr.end(), 0, [](int s, int v) { return s^v; });
}

Haskell:

1

search = foldl xor 0

Better than linear

A better-than-linear solution requires \(O(LogN)\) time. It applies a variation of binary search.

All elements before the odd occurrence have the first occurrence at even index [0, 2, ..]. After the odd element they follow the opposite pattern, with the first occurrence at odd index [1, 3, ..].

When we divide the space in two halves we check if the middle index is even or odd:

• if even, we check if the underlying element is the same as the next one:
  • if so, the pattern is maintained and we search the right side
  • otherwise, the pattern has been broken somewhere before so we search the left side
• if odd, we basically do the opposite of the idea above. This time we check the element before it:
  • if the same, the pattern is maintained and we search the right side
  • otherwise, the pattern has been broken somewhere before so we search the left side.

Here is an implementation (courtesy of GeeksForGeeks):

 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

void search(const vector<int>& v, int low, int high, int& elem)
{
    // Base cases
    if (low > high)
        return;
    if (low == high)
    {
        elem = v[low];
        return;
    }

    // Find the middle point
    int mid = (low + high) / 2;

    // If mid is even and element next to mid is
    // same as mid, then output element lies on
    // right side, else on left side
    if (mid % 2 == 0)
    {
        if (v[mid] == v[mid + 1])
            search(v, mid + 2, high, elem);
        else
            search(v, low, mid, elem);
    }
    else // If mid is odd
    {
        if (v[mid] == v[mid - 1])
            search(v, mid + 1, high, elem);
        else
            search(v, low, mid - 1, elem);
    }
}

Here is an alternative iterative version in Python by Serena Ziviani:

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

t = int(input().strip())

for i in range(t):
    n = int(input().strip())
    li = [int(tmp) for tmp in input().strip().split(' ')]

    start = 0
    end = len(li)
    while True:
        if end - start == 1:
            print(li[start])
            break
        # Get an even pivot somewhere in the middle
        pivot = (end - start) // 2
        if pivot % 2 == 1:
            pivot +=1
        pivot += start

        if(li[pivot-1] != li[pivot]):
            # go right
            start = pivot
        else:
            # go left
            end = pivot - 1

Alternative version in C++ by Alessandro Pezzato without recursion, with some esoteric optimization using bitwise operators.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int search(const std::vector<int>& arr) {
    int low = 0;
    int high = arr.size() - 1;
    while (low != high) {
        const int mid = (high + low) >> 1;
        if (arr[mid] == arr[mid + 1 - ((mid & 1) << 1)])
            low = mid - (mid & 1) + 2;
        else
            high = mid - (mid & 1);
    }
    return arr[low];
}

This challenge shows that, after all, the binary search pattern can be applied as far as we have a deterministic update rule which moves to only one half of the divided search space.