Find the Missing Number from an Array Containing 1 to N - Java

Category: Medium | Concepts used: Sum formula, XOR properties

---

Problem Statement

Given an array containing N-1 distinct numbers from 1 to N (one number is missing), find the missing one.

Input : [1, 2, 4, 5], N=5      Output: 3

Examples (with edge scenarios)

#	Input Array	N	Output	Why
1	[1, 2, 4, 5]	5	3	3 is missing from 1..5
2	[2, 3, 4, 5]	5	1	The missing number is at the very start of the range
3	[1, 2, 3, 4]	5	5	The missing number is at the very end of the range
4	[]	1	1	Only one possible number (1..1), and it’s missing
5	Large N (e.g., N=100000)	—	—	Watch for integer overflow if summing naively — see note below

Common Fresher Mistake

Mistake	What happens	Fix
Using a HashSet to check “which number from 1..N is not in the array” via a loop	Works, but O(n) extra space when a formula-based approach needs none	Prefer the sum formula or XOR trick for O(1) extra space
Sum overflow for very large N	int sum of 1..N can overflow if N is huge	Use long for the sum calculation if N could be large

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: The Attendance Roll Call

Imagine you are a teacher verifying attendance for a classroom of 5 students labeled 1 to 5:

• Solution 1 (The Weight Balance): You know that if all 5 students were in the classroom, their combined weight would be exactly 15 kg (calculated using the formula 5*(5+1)/2). You ask the students who are actually in the room to step on a scale together. The scale registers 12 kg. By subtracting the actual weight from the expected weight (15 - 12), you immediately know the missing student is student #3!
• Solution 2 (The Key Pairing): You have a box containing 5 unique locker keys (1 to 5), and each student in the room is holding their personal locker key. You place a key from the box and a student’s key in a scanner together; matching keys cancel each other out and dissolve (x ^ x = 0). The only key that remains at the end is key #3, because student #3 was never there to hand in their matching key!

---

Solution 1 — Using the Sum Formula (Recommended)

Intuition

The sum of all numbers from 1 to N has a well-known formula: N*(N+1)/2. If we know what the complete sum should be, and we compute the actual sum of the given (incomplete) array, the difference between them must be exactly the missing number — because everything else cancels out.

public class MissingNumberSum {
    public static int findMissing(int[] arr, int n) {
        int expectedSum = n * (n + 1) / 2; // sum of 1 to n

int actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }

return expectedSum - actualSum;
    }

public static void main(String[] args) {
        System.out.println(findMissing(new int[]{1, 2, 4, 5}, 5)); // 3
        System.out.println(findMissing(new int[]{2, 3, 4, 5}, 5)); // 1
        System.out.println(findMissing(new int[]{1, 2, 3, 4}, 5)); // 5
    }
}

Output:

3
1
5

Dry Run (arr = [1, 2, 4, 5], n = 5)

expectedSum = 5*6/2 = 15
actualSum = 1+2+4+5 = 12
missing = 15 - 12 = 3

Interviewer’s take

This is the expected, elegant solution — O(n) time, O(1) extra space, and shows familiarity with the sum-of-first-N-numbers formula, a very handy tool across many array/math problems.

Follow-up questions you might get:

• “What if N is very large and the sum could overflow an int?” → Switch expectedSum and actualSum to long to avoid overflow.
• “Can you think of an alternative that avoids summation entirely?” → leads to Solution 2 (XOR).

---

Solution 2 — Using XOR (Avoids Overflow Entirely)

Intuition

XOR has a useful cancellation property: x ^ x = 0, and XOR-ing a set of numbers with itself (in any order) cancels matching pairs out to zero. If we XOR together all numbers from 1 to N, AND also XOR together all numbers actually present in the array, every number that appears in both sets cancels out — leaving only the one number that was in the “should exist” set but not in the “actually present” set: the missing number.

public class MissingNumberXOR {
    public static int findMissing(int[] arr, int n) {
        int xorAll = 0;

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

// XOR all numbers actually present in the array
        for (int num : arr) {
            xorAll ^= num;
        }

// whatever is left is the missing number (its "partner" never appeared)
        return xorAll;
    }

public static void main(String[] args) {
        System.out.println(findMissing(new int[]{1, 2, 4, 5}, 5)); // 3
    }
}

Output:

3

Dry Run (arr = [1, 2, 4, 5], n = 5)

xorAll = 1^2^3^4^5 (all numbers 1 to 5)
       then also ^= 1^2^4^5 (all numbers in the array)

Combined: (1^1) ^ (2^2) ^ 3 ^ (4^4) ^ (5^5)
        = 0 ^ 0 ^ 3 ^ 0 ^ 0
        = 3  (everything else cancels, only 3 — the missing number — remains)

Interviewer’s take

This is a nice bonus answer — no risk of integer overflow (unlike the sum formula for extremely large N), since XOR never produces a number larger than what’s already in play. Great to mention if the interviewer specifically probes about overflow safety, but Solution 1 (sum formula) is usually the primary expected answer since it’s more intuitive to explain.

---

📊 Visual Flowchart

graph TD
    Start["Input: Array arr of size N-1"] --> MethodSelect{"Choose Method"}
    MethodSelect -->|Sum Formula| SumM["expectedSum = N * (N + 1) / 2<br>actualSum = sum(arr)"]
    SumM --> CalcDiff["missing = expectedSum - actualSum"]
    MethodSelect -->|XOR Cancellation| XORM["xorAll = XOR(1 to N)<br>xorArr = XOR(arr)"]
    XORM --> CalcXOR["missing = xorAll ^ xorArr"]
    CalcDiff --> End["Return missing"]
    CalcXOR --> End

---

Final Verdict — Which Solution Should You Give?

• Solution 1 (sum formula) is the standard, expected answer — easy to explain, efficient.
• Solution 2 (XOR) is a great bonus if asked about overflow safety or alternative techniques — shows deeper knowledge of bitwise properties.

---

Quick Recap

Approach	Time	Space	Overflow risk?
Sum formula	O(n)	O(1)	Possible for very large N (use long)
XOR	O(n)	O(1)	None