Missing or Duplicate Number in an Array

Write a function that will find a missing or duplicated number in an array.

💡Strategies for Solving This Problem

Multiple Solutions, Different Trade-offs

I've gotten variants of this at Amazon and Microsoft. The problem: array of n numbers from 1 to n, one is missing or duplicated. Find it.

Approach 1: Math Formula (Cleanest)

Sum of 1 to n is: n(n+1)/2

Expected sum - actual sum = missing number (or duplicate with negative)

This is O(n) time, O(1) space. My go-to solution.

Approach 2: XOR Bit Manipulation (Clever)

XOR has cool properties:

a ⊕ a = 0
a ⊕ 0 = a
XOR is commutative and associative

XOR all numbers 1 to n, then XOR with array elements. Result is the missing/duplicate number.

Also O(n) time, O(1) space, but shows you know bit tricks.

Approach 3: Hash Set (Straightforward)

Put all numbers in a Set, then check which from 1 to n is missing.

O(n) time, O(n) space. Works but uses extra space.

Approach 4: In-Place Marking (Tricky)

Use array indices as a hash. For each number, mark array[number] as negative. The index that stays positive (or goes negative twice) is your answer.

O(n) time, O(1) space, but modifies the array.

Which to Use?

I usually start with the math approach (it's cleanest). If interviewer asks to optimize or show another method, I'll do XOR. Hash set is the fallback if I'm blanking.

✅Solution

Solution 1: Math Formula (Simplest)

function findMissing(arr, n) {
    // Expected sum of 1 to n
    const expectedSum = n * (n + 1) / 2;

    // Actual sum of array
    const actualSum = arr.reduce((sum, num) => sum + num, 0);

    return expectedSum - actualSum;
}

// Test
console.log(findMissing([1, 2, 4, 5], 5));  // 3
console.log(findMissing([1, 2, 3, 4], 5));  // 5
console.log(findMissing([2, 3, 4, 5], 5));  // 1

For Finding Duplicate

function findDuplicate(arr) {
    const n = arr.length - 1;  // Array has n+1 elements with one duplicate
    const expectedSum = n * (n + 1) / 2;
    const actualSum = arr.reduce((sum, num) => sum + num, 0);

    return actualSum - expectedSum;  // Duplicate number
}

console.log(findDuplicate([1, 2, 3, 4, 4]));  // 4
console.log(findDuplicate([1, 1, 2, 3, 4]));  // 1

Solution 2: XOR Bit Manipulation

function findMissingXOR(arr, n) {
    let xor = 0;

    // XOR all numbers from 1 to n
    for (let i = 1; i <= n; i++) {
        xor ^= i;
    }

    // XOR with all array elements
    for (let num of arr) {
        xor ^= num;
    }

    // Result is the missing number
    // (all others cancel out because a ^ a = 0)
    return xor;
}

// More concise version
function findMissingXORConcise(arr, n) {
    let xor = 0;
    for (let i = 1; i <= n; i++) xor ^= i;
    for (let num of arr) xor ^= num;
    return xor;
}

console.log(findMissingXOR([1, 2, 4, 5], 5));  // 3

Why XOR Works

Example: Find missing in [1, 2, 4, 5], n=5

XOR 1 to 5:  1 ^ 2 ^ 3 ^ 4 ^ 5
XOR array:   1 ^ 2 ^ 4 ^ 5

Combined:    1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 1 ^ 2 ^ 4 ^ 5
             = (1^1) ^ (2^2) ^ 3 ^ (4^4) ^ (5^5)
             = 0 ^ 0 ^ 3 ^ 0 ^ 0
             = 3

All paired numbers cancel (a ^ a = 0), leaving only the missing number.

Solution 3: Hash Set

function findMissingSet(arr, n) {
    const seen = new Set(arr);

    for (let i = 1; i <= n; i++) {
        if (!seen.has(i)) {
            return i;
        }
    }

    return -1;  // Not found (shouldn't happen with valid input)
}

console.log(findMissingSet([1, 2, 4, 5], 5));  // 3

Solution 4: In-Place Marking (Most Complex)

function findMissingInPlace(arr) {
    const n = arr.length + 1;

    // Mark indices by making them negative
    for (let i = 0; i < arr.length; i++) {
        const index = Math.abs(arr[i]) - 1;

        if (index < arr.length) {
            arr[index] = -Math.abs(arr[index]);
        }
    }

    // Find the positive index (or unmapped)
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > 0) {
            return i + 1;
        }
    }

    return n;  // Last number is missing
}

// Note: This modifies the array!
let test = [1, 2, 4, 5];
console.log(findMissingInPlace(test));  // 3
console.log(test);  // Array is now modified

Comparison

Method	Time	Space	Pros	Cons
Math	O(n)	O(1)	Cleanest	Overflow risk for large n
XOR	O(n)	O(1)	No overflow, shows bit skills	Less intuitive
Hash Set	O(n)	O(n)	Easy to understand	Extra space
In-place	O(n)	O(1)	Space efficient	Modifies array

Edge Cases

n = 1: Array is empty, missing is 1
Missing last number: All methods handle this
Large n: Math approach might overflow, XOR is safer
Array not sorted: All methods work regardless

Interview recommendation: Start with math approach (clean and intuitive). If asked for another method, use XOR (shows bit manipulation knowledge).