우선 하나의 해법으로 모든 배열 요소의 합을 구한 후, 1부터 백만까지의 숫자를 모두 더한 값을 수학적으로 구하여 이를 빼면 무엇이 하나 더 들어 있는지를 알 수 있다. 수학적으로 1부터 N까지의 합은 N * (N+1) / 2 공식을 통해 구할 수 있다.

int SumMethod(int[] A) 
{            
    int sum = 0;
    for (int i = 0; i < A.Length; i++)
    {
        sum += A[i];
    }

    int n = A.Length - 1;
    int expectedSum = n * (n + 1) / 2;

    return sum - expectedSum;
}

하지만, 이러한 해법은 한가지 치명적인 문제가 있는데, 만약 배열이 100만이 아니라 1000만이 된다면, Overflow가 발생한다는 것이다. 물론 이 경우 sum 타입을 int가 long으로 하면 일시적으로 해결할 수는 있지만, 또다시 입력 숫자가 커진다면 계속 문제가 발생할 수 있다.

Overflow가 발생하지 않는 다른 해법으로 XOR를 사용하는 방식을 생각해 볼 수 있다.

int XorMethod(int[] A)
{
    int r = 0;
    for (int i = 0; i < A.Length; i++)
    {
        r = r ^ A[i] ^ i;
    }
    return r;
}

XOR는 동일한 숫자를 XOR하면 0가 되는 성질이 있다. 따라서, 1부터 100만까지의 루프를 돌면서 for 루프의 i와 배열 A[i]를 XOR하면 1부터 100만까지의 동일한 숫자는 0가 되고 중복된 숫자만 하나 남게 된다. 예를 들어, 배열에 1부터 10까지 들어 있고 하나면 중복된 숫자가 들어 있다면, 아래와 같이 들어 있다고 볼 수 있다. (물론 실제 A[i]는 순서는 소트되지 않고 랜덤하게 있겠지만 XOR 연산에서 이는 중요하지 않다)

 i  :   0   1   2   3   4   5   6  7  8  9  10 
A[i]:   1   2   3   3   4   5   6  7  8  9  10

i의 1과 A[0]의 1은 서로 상쇄되고, i=2와 A[1]=2는 서로 상쇄된다. 이런 식으로 지우다 보면, 중복값 A[3]=3과 i=0만 남게 되는데 이를 XOR하면 중복값 3을 구할 수 있다.