Missing or Duplicate Number in an Array: XOR, Floyd, Cyclic Sort

Missing or Duplicate Number in an Array: XOR, Sum, Cyclic Sort, and Floyd’s Algorithm

Finding the missing number or the duplicate number in an array of integers is a foundational problem family asked at FAANG, AI labs, and most coding interviews. The variants — single missing in [0, n], single duplicate in [1, n], multiple missing, multiple duplicates — share a common toolkit: XOR tricks, arithmetic sums, cyclic sort, hash sets, and Floyd’s cycle detection. This guide covers the standard approaches with working code, when to use each, and the trade-offs in time and space.

Variant 1: Missing Number in [0, n]

(LeetCode #268) Given an array of n distinct numbers in the range [0, n], find the one number missing from the range.

Approach: Sum formula

Sum of [0, n] is n(n+1)/2. Subtract the array sum to get the missing number.

def missing_number_sum(nums: list[int]) -> int:
    """O(n) time, O(1) space."""
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

Risk: integer overflow in languages without arbitrary precision integers. Python is safe; C++ and Java may overflow for large n.

Approach: XOR

XOR all numbers in [0, n] with all numbers in the array. Pairs cancel; the unmatched value is the missing number. Avoids overflow.

def missing_number_xor(nums: list[int]) -> int:
    """O(n) time, O(1) space — no overflow risk."""
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

Why XOR works: XOR is associative, commutative, and self-inverse (x ^ x = 0; x ^ 0 = x). XOR-ing all expected values with all actual values cancels everything except the missing one.

Variant 2: Duplicate Number in [1, n]

(LeetCode #287) Given an array of n+1 integers in [1, n], find the duplicate without modifying the array, in O(1) space and O(n) time.

Approach: Floyd’s Cycle Detection

Treat the array as a function: index i “points to” nums[i]. The duplicate creates a cycle. Floyd’s algorithm finds the cycle entry, which is the duplicate.

def find_duplicate(nums: list[int]) -> int:
    """O(n) time, O(1) space, no array modification."""
    slow = fast = nums[0]

    # Phase 1: detect cycle
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Phase 2: find cycle entry
    pointer = nums[0]
    while pointer != slow:
        pointer = nums[pointer]
        slow = nums[slow]
    return pointer

Why this works: Treating nums[i] as the next pointer creates a graph. Since values are in [1, n] and there are n+1 elements, by pigeonhole at least one value repeats. The duplicate creates two indices that map to the same next-value, forming a cycle. The cycle entry is the duplicate.

Approach: Hash set (O(n) space)

def find_duplicate_set(nums: list[int]) -> int:
    """O(n) time, O(n) space."""
    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)
    return -1

Simpler but uses extra space. Acceptable as a warm-up; interviewers will push for O(1) space.

Approach: Sort then scan (O(n log n))

def find_duplicate_sort(nums: list[int]) -> int:
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return nums[i]
    return -1

Modifies the array (often disallowed). O(n log n) time. Mention as an alternative; not the expected answer.

Variant 3: Multiple Missing in [1, n]

(LeetCode #448) Find all numbers in [1, n] that don’t appear in the array.

Approach: Cyclic sort / negation marking

Use the array itself as a hash. For each value v, negate nums[v - 1] (mark that v is present). After processing, indices with positive values are missing.

def find_disappeared_numbers(nums: list[int]) -> list[int]:
    """O(n) time, O(1) extra space (output not counted)."""
    for i in range(len(nums)):
        idx = abs(nums[i]) - 1
        if nums[idx] > 0:
            nums[idx] = -nums[idx]
    return [i + 1 for i, v in enumerate(nums) if v > 0]

Modifies the input. Restore by re-iterating with abs() if needed.

Variant 4: Multiple Duplicates in [1, n]

(LeetCode #442) Find all elements that appear twice in an array of n integers in [1, n].

Approach: Negation marking

def find_duplicates(nums: list[int]) -> list[int]:
    """O(n) time, O(1) extra space."""
    result = []
    for i in range(len(nums)):
        idx = abs(nums[i]) - 1
        if nums[idx] < 0:
            result.append(idx + 1)
        else:
            nums[idx] = -nums[idx]
    return result

Same negation trick as above; collect the values that get marked twice.

Variant 5: Two Numbers — One Missing, One Duplicate

(LeetCode #645 — Set Mismatch) Given an array originally containing [1, n] but with one value duplicated and one missing, find both.

Approach: XOR variant

XOR the array with [1, n]. The result is missing ^ duplicate. Find a bit where they differ; partition both groups by that bit; XOR each group separately.

def find_error_nums(nums: list[int]) -> list[int]:
    """O(n) time, O(1) space."""
    n = len(nums)
    xor_all = 0
    for i in range(1, n + 1):
        xor_all ^= i
    for num in nums:
        xor_all ^= num
    # xor_all = missing ^ duplicate; partition by lowest set bit
    diff_bit = xor_all & -xor_all
    a = b = 0
    for i in range(1, n + 1):
        if i & diff_bit:
            a ^= i
        else:
            b ^= i
    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num
    # a and b are missing and duplicate; figure out which
    duplicate = a if a in nums else b
    missing = b if duplicate == a else a
    return [duplicate, missing]

Tricky implementation; rarely required in interviews. The hash-set or sum-and-sum-of-squares approach is easier and acceptable.

Common Mistakes

• Integer overflow on the sum approach. n(n+1)/2 grows with n²; for n = 10⁵, the sum is ~5×10⁹ which fits in 64-bit int but not 32-bit. Use 64-bit or XOR to avoid the issue.
• Modifying input when not allowed. The negation-marking approach mutates the array. If the problem requires preserving input, use Floyd’s algorithm or a hash set.
• Off-by-one in range. Some problems use [0, n], others [1, n]. Check the range before applying any approach; the index calculations differ.
• Forgetting the cycle detection edge cases. Floyd’s algorithm assumes a cycle exists. If the input is malformed (no duplicate), the algorithm doesn’t terminate. Add a sanity check or rely on the problem’s guarantees.
• Confusing XOR with set difference. XOR finds elements appearing an odd number of times; for finding the missing single element when all others appear exactly twice, XOR is perfect. For finding multiple missings or duplicates, XOR alone isn’t enough — you need bit partitioning or other tricks.

Frequently Asked Questions

See also: Two Sum: Find a Pair in an Array • Check if a Number is a Power of Two • Detect a Cycle in a Linked List

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

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

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

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

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

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