Missing Number — Gauss Formula and XOR Trick [LC 268]

Problem Statement#

Given an array nums containing n distinct numbers in the range [0, n], return the one number in the range that is missing.

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n
• All numbers in nums are unique

Input:  nums = [3,0,1]
Output: 2

Input:  nums = [9,6,4,2,3,5,7,0,1]
Output: 8

Why This Problem Matters#

LeetCode 268 is a screening-round favorite at Amazon, Microsoft, and Google. It is simple enough to solve in minutes but opens up into multiple approaches — Gauss formula, XOR, cyclic sort — that let an interviewer probe how deeply you understand mathematical properties of arrays.

The Gauss sum trick appears in many follow-up problems: Find All Numbers Disappeared in an Array (LC 448), Find the Duplicate Number (LC 287), and First Missing Positive (LC 41) all extend this core idea of "what should be here vs what is here." This is a foundational array problem every candidate should master cold.

The Core Insight#

Gauss formula approach: The sum of integers from 0 to n is n * (n + 1) / 2. Compute this expected sum, subtract the actual sum of the array. The difference is the missing number.

XOR approach: XOR all numbers from 0 to n, then XOR all elements in nums. Each number that appears in both cancels out (x XOR x = 0), leaving only the missing number.

Both approaches run in O(n) time and O(1) space — no sorting, no hash set needed.

Visual Dry Run#

nums = [3, 0, 1], n = 3

Gauss formula:

• Expected sum: 3 * 4 / 2 = 6
• Actual sum: 3 + 0 + 1 = 4
• Missing: 6 - 4 = 2

XOR:

• XOR of 0..3: 0 XOR 1 XOR 2 XOR 3 = 0
• XOR with array: 0 XOR 3 XOR 0 XOR 1 = 2
• The number 2 never appears to cancel itself out — result is 2

Solution (Optimal)#

class Solution:
    def missingNumber(self, nums):
        n = len(nums)
        return n * (n + 1) // 2 - sum(nums)

var missingNumber = function(nums) {
    const n = nums.length;
    const expected = n * (n + 1) / 2;
    const actual = nums.reduce((acc, x) => acc + x, 0);
    return expected - actual;
};

Time: O(n) — one pass to sum the array Space: O(1) — only scalar variables

Common Mistakes#

• Using a hash set — works in O(n) time but uses O(n) space unnecessarily
• Sorting the array — O(n log n) and modifies input, both avoidable
• Integer overflow for large n — in languages like Java/C++, use long for n * (n + 1) / 2
• Off-by-one in the Gauss formula — it's n * (n + 1) / 2 for 0..n, not n * (n - 1) / 2
• XOR approach bugs — must XOR with all of 0..n, not 1..n (0 is in the range)

Interview Tips#

• Present both approaches: "Gauss formula is the most readable; XOR is the bit-manipulation flex"
• State the complexity upfront: "O(n) time, O(1) space — no extra memory needed"
• Mention the cyclic sort approach if asked for a third method (place each number at its index, find the mismatched position)
• Note that the Gauss formula can have overflow issues in integer-limited languages — always mention this
• Connect to follow-up problems: Find All Missing Numbers (LC 448) and Find the Duplicate (LC 287)

Follow-up Questions#

• What if there are two missing numbers? (XOR or Gauss approach needs modification — split into two groups by a bit, or use sum and sum-of-squares)
• What if the range is 1 to n instead of 0 to n? (Change expected sum to n * (n + 1) / 2 vs current sum over the n-1 elements)
• What if the array can contain duplicates? (The problem guarantees uniqueness — with duplicates, this becomes a different problem)
• Can you solve it in O(1) space without Gauss formula? (Yes — XOR approach also O(1) space)
• How does this extend to Find All Numbers Disappeared in an Array (LC 448)? (Mark visited indices by negation or use cyclic sort to place each element at its correct index)

Key Takeaways#

• LeetCode 268 is asked at Amazon, Microsoft, and Google — a foundational easy problem with multiple O(1) space solutions
• Gauss formula: missing = n*(n+1)/2 - sum(nums) — cleanest and most readable approach
• XOR approach: missing = XOR(0..n) XOR XOR(nums) — each present number cancels itself out
• Both approaches: O(n) time, O(1) space — no hash set or sorting needed
• Watch for integer overflow in the Gauss formula when n is large (use long in Java/C++)
• The "expected vs actual" mindset — Gauss sum, XOR identity — generalizes to Find the Duplicate, Find All Missing Numbers, and First Missing Positive
• Cyclic sort is a third approach: place each element at its correct index, then find the slot that doesn't match