Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Single Number

Easy · Arrays · Asked at Amazon, Google, TCS

Every element appears twice except one. Find that single element.

Input

First line: n. Second line: n space-separated integers.

Output

The element that appears once.

Constraints

XOR of all elements gives the answer in O(1) extra space (x ^ x = 0).

Example 1

Input

3
2 2 1

Output

1

Example 2

Input

5
4 1 2 1 2

Output

4

Hints

  1. What is x ^ x? And x ^ 0?
  2. XOR all the numbers: every pair cancels out, leaving the single one.

Approach

XOR is commutative and x ^ x = 0, x ^ 0 = x. XOR-ing the whole array cancels every value that appears twice and leaves only the unique value. This works for negative numbers too, since XOR acts on the bit pattern.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long result = 0, x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        result ^= x;
    }
    cout << result << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
result = 0
for x in data[1 : data[0] + 1]:
    result ^= x
print(result)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long result = 0;
        for (int i = 0; i < n; i++) result ^= sc.nextLong();
        System.out.println(result);
    }
}

Solve Single Number online · All practice problems