Missing Number

Java coding interview problem for Array Logic: Missing Number.

Finding the missing number in an array is one of the most popular array interview problems.

Although the problem looks simple, it tests important concepts:

Array traversal
Mathematical reasoning
XOR operation
Sorting
Hashing
Space optimization
Bit manipulation

This problem is a foundation for many advanced concepts:

Finding duplicates
Data validation
Missing records detection
Frequency analysis
Bit manipulation problems

What is the Missing Number Problem?

Given an array containing n distinct numbers from the range:

0 to n

find the only missing number.

Example 1

Input:

nums = [3,0,1]

Numbers should contain:

0,1,2,3

Missing value:

Output:

Example 2

Input:

nums = [0,1]

Expected range:

0,1,2

Missing:

Output:

Example 3

Input:

nums = [9,6,4,2,3,5,7,0,1]

Expected range:

0 to 9

Missing:

Output:

Why is This Question Asked in Interviews?

Interviewers ask this problem because it evaluates:

Understanding of array ranges
Optimization skills
Mathematical thinking
Bit manipulation knowledge

Common variations:

Find duplicate number
Find missing and duplicate number
Find first missing positive number
Find missing ranges
Find missing IDs in database records

Real-World Applications

Database Record Validation

Suppose user IDs should be:

0,1,2,3,4

Database contains:

[0,1,3,4]

Missing record:

File Processing Systems

Files may have sequential IDs:

Missing:

Distributed Systems

Detect missing events in event streams.

Example:

Expected events:

1,2,3,4,5

Received:

1,2,4,5

Missing event:

Data Synchronization

Finding missing records between systems.

Problem Statement

Given an integer array containing n distinct numbers from:

0 to n

return the missing number.

Constraints

Example constraints:

1 <= n <= 10000

Rules:

Numbers are unique.
Only one number is missing.
Values are between 0 and n.

Understanding Missing Number Logic

Consider:

Input:

[3,0,1]

Length:

n = 3

Expected numbers:

0,1,2,3

Available:

0,1,3

Missing:

Array Visualization

Expected:

Index:

0 1 2 3

0 1 2 3

Actual:

0 1 _ 3

Missing:

Mathematical Concept

For numbers:

0 + 1 + 2 + ... + n

The sum is:

n * (n + 1) / 2

Example:

Expected sum:

3 * 4 / 2

Result:

Array sum:

3 + 0 + 1 = 4

Missing:

6 - 4 = 2

Dry Run

Input:

[3,0,1]

Step 1:

Array length:

n = 3

Step 2:

Calculate expected sum:

3 * (3+1) / 2

Step 3:

Calculate actual sum:

3 + 0 + 1

Step 4:

Difference:

6 - 4

Result:

Approach 1 — Brute Force Search

The simplest approach is checking every number from:

0 to n

and finding which one is missing.

Algorithm

Find array length.
For every number from 0 to n:
- Search in array.
If not found, return that number.

Java Program

public class MissingNumberBruteForce {


    public static int findMissing(
            int[] numbers) {


        int n = numbers.length;


        for (int value = 0;
             value <= n;
             value++) {


            boolean found = false;


            for (int number : numbers) {


                if (number == value) {

                    found = true;

                    break;

                }

            }


            if (!found) {

                return value;

            }

        }


        return -1;

    }


    public static void main(String[] args) {


        int[] numbers =
                {3,0,1};


        System.out.println(
                findMissing(numbers));

    }

}

Output

Step-by-Step Explanation

Input:

[3,0,1]

Check:

Exists?

Yes

Check:

Exists?

Yes

Check:

Exists?

No

Return:

Complexity Analysis

Time:

O(n²)

Because every number searches the complete array.

Space:

O(1)

Advantages

Very easy to understand.
No additional memory.
Good for beginners.

Drawbacks

Very slow for large arrays.
Too many comparisons.
Not suitable for production.

Approach 2 — Sorting Approach

Another solution is sorting the array first.

After sorting:

Numbers should appear in increasing order.
The first mismatch gives the missing number.

Example

Input:

[3,0,1]

Sort:

[0,1,3]

Expected:

[0,1,2,3]

Mismatch:

Missing:

Algorithm

Sort the array.
Traverse from index 0.
Compare:

numbers[i] != i

Return mismatch.
If no mismatch, return n.

Java Program

import java.util.Arrays;

public class MissingNumberSorting {


    public static int findMissing(
            int[] numbers) {


        Arrays.sort(numbers);


        for (int i = 0;
             i < numbers.length;
             i++) {


            if (numbers[i] != i) {

                return i;

            }

        }


        return numbers.length;

    }


    public static void main(String[] args) {


        int[] numbers =
                {3,0,1};


        System.out.println(
                findMissing(numbers));

    }

}

Output

Complexity Analysis

Sorting:

O(n log n)

Traversal:

O(n)

Overall:

O(n log n)

Space:

O(1)

(depends on sorting implementation)

Advantages

Easy to implement.
Uses sorting knowledge.
Better than brute force.

Drawbacks

Sorting is unnecessary work.
Modifies original array.
Not the optimal interview solution.

Approach 3 — Sum Formula Approach (Optimal)

The mathematical approach uses the formula:

Sum of numbers 0 to n:

n(n+1)/2

Missing number:

Expected Sum - Actual Sum

Java Program

public class MissingNumberSum {


    public static int findMissing(
            int[] numbers) {


        int n = numbers.length;


        int expectedSum =
                n * (n + 1) / 2;


        int actualSum = 0;


        for (int number : numbers) {

            actualSum += number;

        }


        return expectedSum - actualSum;

    }


    public static void main(String[] args) {


        int[] numbers =
                {3,0,1};


        System.out.println(
                findMissing(numbers));

    }

}

Output

Step-by-Step Explanation

Input:

[3,0,1]

Length:

n = 3

Expected:

0+1+2+3

Formula:

3*4/2

Result:

Actual:

3+0+1

Result:

Missing:

6-4

Result:

Complexity Analysis

Time:

O(n)

Space:

O(1)

Advantages

Simple.
Fast.
Constant memory.
Better than sorting.

Drawbacks

Integer overflow possible for very large n.
Requires mathematical understanding.

Approach 4 — XOR Approach (Best Interview Solution)

The XOR approach is one of the most popular solutions for the Missing Number problem.

It uses the properties of the XOR (^) operator.

This approach provides:

O(n) time
O(1) space
No overflow issue

XOR Properties

The XOR operator follows these rules:

Property 1

Any number XOR itself is zero.

a ^ a = 0

Example:

5 ^ 5 = 0

Property 2

Any number XOR zero is the number itself.

a ^ 0 = a

Example:

5 ^ 0 = 5

Property 3

XOR is associative.

(a ^ b) ^ c

=

a ^ (b ^ c)

XOR Logic for Missing Number

Given:

Numbers range:

0 to n

We XOR:

All numbers from:

0 to n

All numbers present in array.

The numbers that exist cancel each other.

Only the missing number remains.

Example

Input:

[3,0,1]

Expected numbers:

0,1,2,3

XOR all expected:

0 ^ 1 ^ 2 ^ 3

XOR array:

3 ^ 0 ^ 1

Combine:

0 ^ 1 ^ 2 ^ 3 ^ 3 ^ 0 ^ 1

Cancel duplicates:

Remaining:

Missing number:

Java Program

public class MissingNumberXOR {


    public static int findMissing(
            int[] numbers) {


        int n = numbers.length;


        int xor = n;


        for (int i = 0;
             i < n;
             i++) {


            xor ^= i;

            xor ^= numbers[i];

        }


        return xor;

    }


    public static void main(String[] args) {


        int[] numbers =
                {3,0,1};


        System.out.println(
                findMissing(numbers));

    }

}

Output

Step-by-Step Explanation

Input:

[3,0,1]

Length:

n = 3

Initialize:

xor = 3

Iteration 1:

i = 0

XOR:

3 ^ 0 ^ 3

Result:

Iteration 2:

i = 1

XOR:

0 ^ 1 ^ 0

Result:

Iteration 3:

i = 2

XOR:

1 ^ 2 ^ 1

Result:

Return:

Complexity Analysis

Time:

O(n)

Space:

O(1)

Advantages

Best interview solution.
No extra memory.
No integer overflow.
Single traversal.

Drawbacks

XOR logic is less intuitive.
Requires bit manipulation knowledge.

Mathematical Proof of XOR Solution

Expected numbers:

0,1,2,...,n

Array values:

a1,a2,...,an

XOR operation:

(0^1^2...^n)
^

(a1^a2...^an)

Every existing number appears twice.

Because:

x ^ x = 0

All existing values disappear.

Only missing value remains.

Approach 5 — Using HashSet

Another simple solution is using a HashSet.

The idea:

Store all array elements.
Check every number from 0 to n.
Return the number not found.

Algorithm

Create HashSet.
Add array elements.
Loop from:

0 to n

Check existence.
Return missing value.

Java Program

import java.util.HashSet;
import java.util.Set;

public class MissingNumberHashSet {


    public static int findMissing(
            int[] numbers) {


        Set<Integer> set =
                new HashSet<>();


        for (int number : numbers) {

            set.add(number);

        }


        for (int i = 0;
             i <= numbers.length;
             i++) {


            if (!set.contains(i)) {

                return i;

            }

        }


        return -1;

    }


    public static void main(String[] args) {


        int[] numbers =
                {3,0,1};


        System.out.println(
                findMissing(numbers));

    }

}

Output

Complexity Analysis

Time:

O(n)

Space:

O(n)

Advantages

Very easy to understand.
Good for beginners.
No mathematical knowledge required.

Drawbacks

Extra memory required.
Hashing overhead.

Approach 6 — Using Java Streams

Java Streams can also solve this problem.

The approach:

Create a range from 0 to n.
Check which value is missing.
Return it.

Java Program

import java.util.Arrays;
import java.util.stream.IntStream;

public class MissingNumberStreams {


    public static int findMissing(
            int[] numbers) {


        return IntStream.rangeClosed(
                    0,
                    numbers.length)
                .filter(
                    value ->
                        Arrays.stream(numbers)
                        .noneMatch(
                            number ->
                                number == value))
                .findFirst()
                .orElse(-1);

    }


    public static void main(String[] args) {


        int[] numbers =
                {3,0,1};


        System.out.println(
                findMissing(numbers));

    }

}

Output

Complexity Analysis

Time:

O(n²)

Because:

Outer stream checks every value.
Inner stream scans array.

Space:

O(1)

Advantages

Functional programming style.
Compact code.

Drawbacks

Less efficient.
Not recommended for large arrays.
More difficult to debug.

Comparison of All Approaches

Approach	Time Complexity	Space Complexity	Interview Rating
Brute Force	O(n²)	O(1)	⭐⭐
Sorting	O(n log n)	O(1)	⭐⭐⭐
Sum Formula	O(n)	O(1)	⭐⭐⭐⭐
XOR	O(n)	O(1)	⭐⭐⭐⭐⭐
HashSet	O(n)	O(n)	⭐⭐⭐⭐
Streams	O(n²)	O(1)	⭐⭐⭐

Sum Formula vs XOR

Feature	Sum Formula	XOR
Time	O(n)	O(n)
Space	O(1)	O(1)
Overflow Risk	Yes	No
Easy to Understand	Yes	Medium
Interview Preference	Good	Excellent

Handling Edge Cases

Case 1 — Empty Array

Input:

[]

Expected range:

[0]

Output:

Case 2 — Missing Last Number

Input:

[0,1,2]

Missing:

Output:

Case 3 — Missing First Number

Input:

[1,2,3]

Output:

Case 4 — Single Element

Input:

[0]

Output:

Common Interview Mistakes

Mistake 1

Using incorrect range.

Wrong:

1 to n

Correct:

0 to n

Mistake 2

Forgetting that array length is:

but range contains:

n + 1 numbers

Mistake 3

Integer overflow with sum formula.

Example:

n * (n + 1)

For large values, use:

long

Mistake 4

Sorting unnecessarily.

Sorting works but changes:

Original order
Complexity

Mistake 5

Using HashSet when memory is limited.

Prefer:

XOR

Interview Follow-up Questions

Q1. Find two missing numbers.

Q2. Find missing and duplicate number.

Q3. Find first missing positive integer.

Q4. Find missing numbers in range.

Q5. Solve without extra space.

Q6. Explain XOR approach.

Q7. Why does XOR avoid overflow?

Q8. Find missing IDs from database records.

Key Takeaways

Missing Number is a classic array problem.
Multiple solutions exist.

For interviews:

Beginner:

HashSet

Mathematical:

Sum Formula

Optimal:

XOR

Remember:

a ^ a = 0

a ^ 0 = a

XOR removes all existing numbers and leaves only the missing number.

Frequently Asked Interview Questions

Q1. What is the optimal solution?

XOR approach.

Complexity:

Time: O(n)

Space: O(1)

Q2. Why use XOR instead of sum?

Because XOR avoids integer overflow.

Q3. Can sorting solve this problem?

Yes.

But complexity becomes:

O(n log n)

Q4. Which solution should be used in production?

Depends:

Simple code → Sum Formula
Large numbers → XOR
Memory restricted → XOR
Beginner readability → HashSet

Interview Tip

When asked:

"Find the missing number."

Explain your thought process:

Brute Force → O(n²)
Sorting → O(n log n)
Sum Formula → O(n)
XOR → O(n), O(1)

The best interview answer:

XOR Approach

Time: O(n)

Space: O(1)

This demonstrates strong understanding of arrays, mathematics, and bit manipulation.