Definition
- Sum method – compute the expected total of 1 through N as
N * (N + 1) / 2, subtract the actual sum of the array, and the difference is the missing number. - XOR method – XOR all indices and values together with the full range so every present number cancels to zero, leaving only the missing one.
- Overflow risk – the sum method can overflow
intfor large N, so uselongfor the accumulator. - Single-missing assumption – both tricks require exactly one number to be missing; for multiple missing numbers, use a different approach.
- Complexity – O(n) time and O(1) space for both methods.
The National Bank of India issues cheque serial numbers 1 through N for Rajesh's cheque book. When the processed cheques come back, exactly one serial is missing. The clerk knows what all serials should total, adds up the returned serials, and the gap is the missing serial number.
Understanding the Concepts
What is the missing number problem?
Given an array that should contain every number from 1 through N but is missing exactly one, find the missing number. This is a classic interview problem with two elegant O(n) solutions: the sum method and the XOR method.
package com.bank.service;
public class MissingNumber {
// Sum method
public static long findMissingSum(int[] arr, int n) {
long expected = (long) n * (n + 1) / 2;
long actual = 0;
for (int val : arr) actual += val;
return expected - actual;
}
// XOR method
public static int findMissingXOR(int[] arr, int n) {
int xor = 0;
for (int i = 1; i <= n; i++) xor ^= i;
for (int val : arr) xor ^= val;
return xor;
}
}
How does the sum method work?
The numbers 1 through N have a closed-form total: N times (N + 1) divided by 2. By summing the array and subtracting from this expected total, the difference is exactly the missing number. This works because subtraction isolates the one value that was not included.
package com.bank.service;
public class SumMethodDemo {
public static void main(String[] args) {
int[] cheques = {1, 2, 4, 5}; // missing 3, n=5
long expected = 5L * 6 / 2; // 15
long actual = 0;
for (int c : cheques) actual += c; // 12
System.out.println("Missing serial: " + (expected - actual)); // 3
}
}
Missing serial: 3
How does the XOR method work?
XOR has a key property: a value XORed with itself is zero, and XOR with zero is the value itself. By XORing every number from 1 to N and every element of the array, each present number appears exactly twice (once in the range and once in the array) and cancels to zero. The missing number appears only once and survives.
package com.bank.service;
public class XORMethodDemo {
public static void main(String[] args) {
int[] cheques = {1, 2, 4, 5}; // missing 3, n=5
int xor = 0;
for (int i = 1; i <= 5; i++) xor ^= i; // 1^2^3^4^5
for (int c : cheques) xor ^= c; // ^1^2^4^5
// 3 appears once, all others cancel
System.out.println("Missing serial: " + xor); // 3
}
}
Missing serial: 3
How is the sum method different from the XOR method?
Both methods find the missing number in linear time and constant space, but they differ in overflow behavior and generalizability.
| Aspect | Sum Method | XOR Method |
|---|---|---|
| Overflow risk | Yes, for large N (use long) | No, bit operation stays in range |
| Formula | N * (N+1) / 2 - actual_sum | XOR range with XOR array |
| Generalization | Can extend with sum-of-squares for 2 missing | Does not extend easily |
| Readability | Very intuitive | Requires XOR knowledge |
| Cross-check | Can run both and compare | Can run both and compare |
// Sum: risks overflow, use long
long expected = (long) n * (n + 1) / 2;
// XOR: no overflow risk
int xor = 0;
for (int i = 1; i <= n; i++) xor ^= i;
What are the edge cases?
Edge cases include the missing number being 1 (first), N (last), and the array being empty (N=1, missing number is 1). Both methods handle all these correctly.
package com.bank.service;
public class MissingEdgeCases {
public static void main(String[] args) {
// Missing is 1 (first)
System.out.println(MissingNumber.findMissingSum(new int[]{2,3,4,5}, 5)); // 1
// Missing is N (last)
System.out.println(MissingNumber.findMissingSum(new int[]{1,2,3,4}, 5)); // 5
// N=1, empty array
System.out.println(MissingNumber.findMissingSum(new int[]{}, 1)); // 1
// XOR cross-check
System.out.println(MissingNumber.findMissingXOR(new int[]{2,3,4,5}, 5)); // 1
}
}
1
5
1
1
What about overflow and how to prevent it?
For large N (e.g., N = 2 billion), the expected sum exceeds the int range. Always compute the formula using long. The XOR method avoids this entirely because XOR is a bitwise operation that stays within the integer range.
// WRONG: int overflow for large N
int expected = n * (n + 1) / 2; // overflows when n > ~46,340
// CORRECT: use long
long expected = (long) n * (n + 1) / 2;
// SAFEST: XOR method, no overflow possible
int xor = 0;
for (int i = 1; i <= n; i++) xor ^= i;
for (int val : arr) xor ^= val;
What if more than one number is missing?
The single-missing assumption is what makes these tricks work. If two numbers are missing, the sum method only tells you their combined total, not each individual value. For two missing numbers, you need both the sum and the sum-of-squares to form a system of two equations. For many missing numbers, use a presence set or the Cyclic Sort pattern.
// Two missing: sum + sum-of-squares system
// sum1 + sum2 = expectedSum - actualSum
// sum1^2 + sum2^2 = expectedSumSq - actualSumSq
// Solve the quadratic to find both.
// For many missing: Cyclic Sort or boolean array
boolean[] present = new boolean[n + 1];
for (int val : arr) present[val] = true;
for (int i = 1; i <= n; i++)
if (!present[i]) System.out.println("Missing: " + i);
How would you apply this in a banking system?
At the National Bank of India, cheque serial numbers 1 through N are issued to Rajesh. When processed cheques return, the reconciliation system finds the one missing serial. For large cheque books, the system uses long for the sum method and runs the XOR method as a cross-check.
package com.bank.service;
public class ChequeReconciliation {
public long findMissingSumCheque(int[] processedSerials, int totalSerials) {
long expected = (long) totalSerials * (totalSerials + 1) / 2;
long actual = 0;
for (int serial : processedSerials) actual += serial;
return expected - actual;
}
public int findMissingXORCheque(int[] processedSerials, int totalSerials) {
int xor = 0;
for (int i = 1; i <= totalSerials; i++) xor ^= i;
for (int serial : processedSerials) xor ^= serial;
return xor;
}
public static void main(String[] args) {
int[] processed = {1, 2, 3, 5, 6, 7, 8, 9, 10};
ChequeReconciliation cr = new ChequeReconciliation();
System.out.println("Missing (sum): " + cr.findMissingSumCheque(processed, 10));
System.out.println("Missing (xor): " + cr.findMissingXORCheque(processed, 10));
}
}
Missing (sum): 4
Missing (xor): 4
What should a senior engineer know?
A senior engineer should know to confirm the inclusive bounds (0..N vs 1..N) before coding, as an off-by-one error is the classic bug. They should also run both methods and cross-check that they agree, flagging corrupt input if they do not. For production, the XOR method is preferred for its overflow safety.
// Senior: always confirm bounds
// 0..N framing: expected = n*(n+1)/2, array length = n
// 1..N framing: expected = n*(n+1)/2, array length = n-1
// Cross-check pattern:
long sumResult = findMissingSum(arr, n);
int xorResult = findMissingXOR(arr, n);
if (sumResult != xorResult) {
throw new IllegalStateException("Corrupt input: methods disagree");
}
Visual Overview
Sum Method:
Expected: 1 + 2 + 3 + 4 + 5 = 15 (formula: 5*6/2)
Actual: 1 + 2 + _ + 4 + 5 = 12
Missing: 15 - 12 = 3
XOR Method:
Range XOR: 1 ^ 2 ^ 3 ^ 4 ^ 5
Array XOR: 1 ^ 2 ^ 4 ^ 5
Combined: (1^1) ^ (2^2) ^ 3 ^ (4^4) ^ (5^5)
= 0 ^ 0 ^ 3 ^ 0 ^ 0
= 3 ← missing number
┌───────────────────────────────────────┐
│ Range: 1 2 3 4 5 │
│ Array: 1 2 _ 4 5 │
│ ▲ │
│ │ │
│ Missing = 3 │
│ Sum: 15 - 12 = 3 │
│ XOR: cancellation leaves 3 │
└───────────────────────────────────────┘
Key Takeaway
Finding the single missing number from 1 through N can be done in linear time and constant space two ways. The sum method computes the expected total using the closed-form formula N * (N + 1) / 2, subtracts the actual sum of the array, and the difference is the missing number. The XOR method XORs the whole range and all the elements so that every present number cancels in pairs and only the missing one survives.
The pitfall I always guard against in the sum method is overflow: for large N the expected total exceeds the int range, so I compute in a long. The XOR method sidesteps overflow entirely because it is a bit operation. In a reconciliation context, I run both and cross-check that they agree, flagging corrupt input if they do not.
These tricks work because exactly one number is missing. If two were missing, the sum would only give their combined total, and I would need a different approach such as a sum-of-squares system. I also always confirm the inclusive bounds (0..N vs 1..N) because an off-by-one there is the classic bug.
At the National Bank of India, I used this to find the single outstanding cheque serial during reconciliation, where Rajesh's cheque book has serial numbers 1 through N and all but one come back processed. The XOR method served as a cross-check for the sum method, catching any corruption in the returned batch.
Remember one sentence: expected sum minus actual sum is the missing number, and XOR cancels all present numbers in pairs, leaving only the missing one.
---