.png)
Find Missing Number in an Array
Problem Statement
Given an array containing n distinct numbers taken from the range 1 to n+1, find the missing number in the array.
- The array contains all numbers from 1 to n+1 except one missing number.
- The goal is to identify the missing number efficiently.
Example 1
Input:
arr = [1, 2, 4, 5, 6]
Output:
3
Explanation:
- Numbers from 1 to 6 are expected.
- Number 3 is missing.
Example 2
Input:
arr = [2, 3, 1, 5]
Output:
4
Explanation:
- Numbers from 1 to 5 are expected.
- Number 4 is missing.
Why This Problem Is Important
- Tests understanding of array indexing and mathematical formulas.
- Common in interviews and coding tests.
- Introduces efficient techniques like sum formula and XOR approach.
Approaches to Solve the Problem
- Using Sum Formula (Efficient) ✅
Using XOR (Efficient) ✅
Approach 1: Using Sum Formula
Idea
Calculate the sum of first n+1 natural numbers:
- Find the sum of elements in the array.
- The missing number = Total Sum - Array Sum.
Time & Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
C Implementation
#include
int main() {
int arr[] = {1, 2, 4, 5, 6};
int n = 5; // number of elements in array
int total = (n + 1) * (n + 2) / 2;
int sum = 0;
for(int i=0;iC++ Implementation
#include
using namespace std;
int main() {
int arr[] = {1, 2, 4, 5, 6};
int n = 5;
int total = (n + 1)*(n + 2)/2;
int sum = 0;
for(int i=0;iJava Implementation
public class MissingNumber {
public static void main(String[] args) {
int[] arr = {1, 2, 4, 5, 6};
int n = arr.length;
int total = (n + 1) * (n + 2) / 2;
int sum = 0;
for(int num : arr) sum += num;
System.out.println("Missing number is: " + (total - sum));
}
}
Python Implementation
arr = [1, 2, 4, 5, 6]
n = len(arr)
total = (n + 1)*(n + 2)//2
missing = total - sum(arr)
print("Missing number is:", missing)
C# Implementation
using System;
class Program {
static void Main() {
int[] arr = {1,2,4,5,6};
int n = arr.Length;
int total = (n+1)*(n+2)/2;
int sum = 0;
foreach(int num in arr) sum += num;
Console.WriteLine("Missing number is: " + (total - sum));
}
}
JavaScript Implementation
let arr = [1,2,4,5,6];
let n = arr.length;
let total = (n+1)*(n+2)/2;
let sum = arr.reduce((a,b)=>a+b,0);
console.log("Missing number is:", total - sum);
Approach 2: Using XOR
Idea
- XOR all numbers from 1 to n+1. Let it be xor1.
- XOR all elements in the array. Let it be xor2.
- Missing number = xor1 ^ xor2.
Reason:
- XOR of same numbers cancels out (a^a = 0).
- The only remaining number after XOR is the missing one.
Time & Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
Python Implementation (XOR Approach)
arr = [1, 2, 4, 5, 6]
n = len(arr)
xor1 = 0
for i in range(1,n+2):
xor1 ^= i
xor2 = 0
for num in arr:
xor2 ^= num
missing = xor1 ^ xor2
print("Missing number is:", missing)
C++ Implementation (XOR Approach)
#include
using namespace std;
int main() {
int arr[] = {1,2,4,5,6};
int n = 5;
int xor1 = 0, xor2 = 0;
for(int i=1;i<=n+1;i++) xor1 ^= i;
for(int i=0;iDry Run (Sum Formula Example)
| Step | Calculation | Result |
|---|---|---|
| Total Sum | 6*(6+1)/2 | 21 |
| Array Sum | 1+2+4+5+6 | 18 |
| Missing | 21 - 18 | 3 |
Summary
Finding the missing number is a classic array problem.
- Sum formula → Simple and fast.
- XOR approach → Very efficient, avoids integer overflow issues.
- Sorting or hashing → Extra space or slower; less preferred.
Time Complexity: O(n)
Space Complexity: O(1)
Mastering this problem is helpful for array manipulation, math-based problems, and interview coding challenges.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
