Find the missing number in a 1 to 10 sequence

You're in a phone screen with Oracle when the interviewer poses what sounds like a trick question: "I have a sequence of numbers from 1 to 10, but one is missing. How do you find it?" It sounds almost too easy, but the real test is whether you reach for a brute-force search or recall a bit of grade-school math that Carl Friedrich Gauss supposedly figured out at age seven. This problem, also known as "Missing Number" on other platforms, is a staple warm-up that checks whether you can think mathematically about arrays.

TL;DR

Calculate the expected sum of 1 through 10 using the formula n * (n + 1) / 2, which gives 55. Then sum all elements in the input array. The difference between expected and actual sums is your missing number. This runs in O(n) time and O(1) space, with no sorting, no extra data structures, and no wasted work.

Why This Problem Matters

Finding a missing number is one of those problems that separates candidates who write code by instinct from those who pause and think about the math first. Interviewers love it because the naive approach (sort, then scan for a gap) works but wastes time, while the optimal approach takes a single pass through the array. The same mathematical reasoning shows up in problems involving duplicate detection, parity checks, and data validation.

Understanding the Problem

We're given an array of 9 integers. These integers are unique values from 1 to 10, with exactly one number absent. The array can be in any order. Our job is to return the missing value.

In the sequence above, the highlighted slot is the missing number we need to find. The input array contains the other nine values, potentially shuffled.

Given: An integer array of length 9 containing unique values from 1 to 10 Return: The single integer from 1 to 10 that does not appear in the array Constraints: O(n) time, O(1) space

Edge Cases

1. Missing 1: The smallest value is absent, so the array contains [2,3,4,5,6,7,8,9,10]
2. Missing 10: The largest value is absent, so the array contains [1,2,3,4,5,6,7,8,9]
3. Shuffled input: The array is not sorted, e.g. [6,7,8,9,10,1,2,4,5] is missing 3

Solution Approach

The Naive Path (and Why to Skip It)

Your first instinct might be to sort the array and walk through it looking for a gap. That works, but sorting costs O(n log n) time. Another idea is to use a HashSet, adding all elements and then checking which number from 1 to 10 is missing. That's O(n) time but O(n) space. We can do better on both counts.

The Gauss Formula

The sum of the first n natural numbers has a closed-form solution: n * (n + 1) / 2. For n = 10, the expected sum is 10 * 11 / 2 = 55. If we sum all elements in the input array, the difference between 55 and that sum must be the missing number, because every other value from 1 to 10 is accounted for.

This runs in O(n) time (one pass to sum the array) and O(1) space (two integer variables). No sorting, no hash maps, no binary search.

Pro tip: In an interview, mention Gauss by name when explaining this formula. It signals that you recognize the mathematical foundation, and interviewers appreciate that level of awareness.

Implementation

Prefer a different language? Jump to solutions in other languages.

Here is the Java solution:

import java.util.*;

public class Solution {
  public int missingNumber(int[] arr) {
    // Sum of 1 to 10 using Gauss formula
    int expectedSum = 10 * (10 + 1) / 2;

    // Sum the elements in the input array
    int actualSum = Arrays.stream(arr).sum();

    // The difference is the missing number
    return expectedSum - actualSum;
  }
}

Let's trace through with the input [1, 2, 4, 5, 6, 7, 8, 9, 10]:

1. expectedSum = 10 * 11 / 2 = 55
2. actualSum = 1 + 2 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 52
3. return 55 - 52 = 3

The missing number is 3. Correct.

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once to compute the sum. The Gauss formula calculation is O(1). Total: O(n), where n is the length of the array (9 in this case).

Space Complexity: O(1)

We use two integer variables, expectedSum and actualSum, regardless of input size. No additional data structures are allocated.

Alternative Approach: XOR

There is another O(n) time, O(1) space solution using the XOR bitwise operator. The property a ^ a = 0 means that XOR-ing a number with itself cancels it out. If you XOR all numbers from 1 to 10 together, then XOR that result with every element in the array, every number that appears in both sets cancels, leaving only the missing number.

public int missingNumberXOR(int[] arr) {
    int xor = 0;
    for (int i = 1; i <= 10; i++) {
        xor ^= i;
    }
    for (int num : arr) {
        xor ^= num;
    }
    return xor;
}

The XOR approach has one practical advantage: it avoids any risk of integer overflow on very large ranges, since XOR never accumulates a growing sum. For this problem with n = 10, overflow is irrelevant, but it is worth mentioning in an interview to demonstrate depth.

Common Pitfalls

1. Off-by-one in the formula: Using n * (n - 1) / 2 instead of n * (n + 1) / 2. The formula sums 1 through n, not 0 through n-1.
2. Hardcoding the wrong n: The sequence goes from 1 to 10, so n = 10. The array has 9 elements (because one is missing), but the formula uses 10.
3. Using a loop for the expected sum: You can loop from 1 to 10 and add, but the closed-form formula is cleaner and runs in O(1) instead of O(n). In an interview, the formula shows mathematical fluency.
4. Sorting first: Sorting works but is slower than necessary. If an interviewer says "Can you do better than O(n log n)?", the sum formula is the answer.

Interview Tips

1. Start with the brute force: Briefly mention you could sort and scan, then immediately say "but we can do this in O(n) time and O(1) space with the sum formula."
2. Write the formula from memory: n * (n + 1) / 2. If you forget, derive it: pair the first and last numbers (1+10=11), second and second-to-last (2+9=11), and so on. There are 5 such pairs, so the sum is 5 * 11 = 55.
3. Mention the XOR alternative: It shows you know more than one approach and understand bitwise operations.
4. Test with boundaries: Walk through the case where 1 is missing and where 10 is missing to verify your solution handles the edges.
5. Generalize: If the interviewer asks "What about 1 to n?", swap the hardcoded 10 with arr.length + 1. Same algorithm, same complexity.

Key Takeaways

• The Gauss formula n * (n + 1) / 2 turns a potentially O(n log n) sorting problem into an O(n) single-pass solution with O(1) space.
• XOR provides an alternative O(n)/O(1) approach that avoids overflow on large ranges, demonstrating bitwise operation knowledge.
• Always check edge cases where the missing number is at the boundary (1 or 10) to confirm your formula handles both ends correctly.
• Generalizing from a fixed range (1 to 10) to an arbitrary range (1 to n) is a natural follow-up; the algorithm stays identical with n = arr.length + 1.
• In interviews, briefly acknowledging the brute-force sort-and-scan approach before jumping to the math solution shows structured problem-solving.

Practice and Related Problems

Once you've nailed this, try these variations that build on the same mathematical reasoning:

• Find duplicate numbers in an array (uses similar sum/XOR tricks)
• Find the unique number (every element appears twice except one, classic XOR problem)
• Two Sum (another array problem that benefits from thinking about complements)

This problem and hundreds more are available on Firecode, where over 50,000 users have prepared for technical interviews and landed jobs at top tech companies. Whether you're warming up for a phone screen or grinding through hard problems, consistent practice with fundamentals like this is what builds real confidence.

Solutions in Other Languages

Python

class Solution:
    def missing_number(self, arr):
        expected_sum = 10 * (10 + 1) // 2
        actual_sum = sum(arr)
        return expected_sum - actual_sum

JavaScript

class Solution {
  missingNumber(arr) {
    const expectedSum = 10 * (10 + 1) / 2;
    const actualSum = arr.reduce((acc, n) => acc + n, 0);
    return expectedSum - actualSum;
  }
}

TypeScript

class Solution {
  missingNumber(arr: number[]): number {
    const expectedSum = 10 * (10 + 1) / 2;
    const actualSum = arr.reduce((acc, n) => acc + n, 0);
    return expectedSum - actualSum;
  }
}

C++

#include <vector>

class Solution {
public:
  int missingNumber(const std::vector<int> &arr) {
    int expectedSum = 10 * (10 + 1) / 2;
    int actualSum = 0;
    for (auto &n : arr) {
      actualSum += n;
    }
    return expectedSum - actualSum;
  }
};

Go

func (s *Solution) MissingNumber(slice []int) int {
    expectedSum := 10 * (10 + 1) / 2
    actualSum := 0
    for _, n := range slice {
        actualSum += n
    }
    return expectedSum - actualSum
}

Scala

class Solution {
  def missingNumber(arr: Array[Int]): Int = {
    val expectedSum = 10 * (10 + 1) / 2
    val actualSum = arr.sum
    expectedSum - actualSum
  }
}

Kotlin

class Solution {
    fun missingNumber(arr: IntArray): Int {
        val expectedSum = 10 * (10 + 1) / 2
        val actualSum = arr.sum()
        return expectedSum - actualSum
    }
}

Swift

class Solution {
    func missingNumber(_ arr: [Int]) -> Int {
        let expectedSum = 10 * (10 + 1) / 2
        let actualSum = arr.reduce(0, +)
        return expectedSum - actualSum
    }
}

Ruby

class Solution
  def missing_number(arr)
    expected_sum = 10 * (10 + 1) / 2
    actual_sum = arr.sum
    expected_sum - actual_sum
  end
end

Rust

impl Solution {
    pub fn missing_number(&self, arr: Vec<i32>) -> i32 {
        let expected_sum = 10 * (10 + 1) / 2;
        let actual_sum: i32 = arr.iter().sum();
        expected_sum - actual_sum
    }
}

C#

using System.Linq;

public class Solution {
    public int missingNumber(int[] arr) {
        int expectedSum = 10 * (10 + 1) / 2;
        int actualSum = arr.Sum();
        return expectedSum - actualSum;
    }
}

Dart

class Solution {
  int missingNumber(List<int> arr) {
    int expectedSum = 10 * (10 + 1) ~/ 2;
    int actualSum = arr.reduce((a, b) => a + b);
    return expectedSum - actualSum;
  }
}

PHP

class Solution {
    public function missingNumber(array $arr): int {
        $expectedSum = 10 * (10 + 1) / 2;
        $actualSum = array_sum($arr);
        return $expectedSum - $actualSum;
    }
}