1.
Using Summation Formula (Mathematical Approach)
Time Complexity: O(n)
Space Complexity: O(1)
The sum of the first n natural numbers is given by the formula:
Sum=n×(n+1)2\text{Sum} = \frac{n \times (n+1)}{2}Sum=2n×(n+1)
If we subtract the sum of the given array from this sum, we get the missing number.
Code:
java
CopyEdit
public int missingNumber(int[] nums) {
int n = nums.length;
int expectedSum = n * (n + 1) / 2;
int actualSum = 0;
for (int num : nums) {
actualSum += num;
return expectedSum - actualSum;
2. Using XOR (Bitwise Approach)
Time Complexity: O(n)
Space Complexity: O(1)
Using XOR properties:
• a ⊕ a = 0 (XOR-ing a number with itself cancels it)
• a⊕0=a
If we XOR all numbers in the array with all numbers from 0 to n, the missing number will be left.
Code:
java
CopyEdit
public int missingNumber(int[] nums) {
int xor = 0;
int n = nums.length;
// XOR all numbers from 0 to n
for (int i = 0; i <= n; i++) {
xor ^= i;
// XOR all numbers in the array
for (int num : nums) {
xor ^= num;
return xor;
3. Using HashSet (Extra Space Approach)
Time Complexity: O(n)
Space Complexity: O(n)
We store all numbers in a HashSet and check which number from 0 to n is missing.
Code:
java
CopyEdit
import java.util.HashSet;
public int missingNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
for (int i = 0; i <= nums.length; i++) {
if (!set.contains(i)) {
return i;
return -1; // This should never be reached
4. Using Sorting (Sorting Approach)
Time Complexity: O(n log n)
Space Complexity: O(1) (if in-place sorting is used)
Sort the array and check which number is missing.
Code:
java
CopyEdit
import java.util.Arrays;
public int missingNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i) {
return i;
return nums.length; // If no number is missing in between, return n
5. Using Cyclic Sort (Index Mapping)
Time Complexity: O(n)
Space Complexity: O(1)
Put each number at its correct index (num[i] = i) and check the missing index.
Code:
java
CopyEdit
public int missingNumber(int[] nums) {
int i = 0;
while (i < nums.length) {
int correctIndex = nums[i];
if (correctIndex < nums.length && nums[i] != nums[correctIndex]) {
// Swap nums[i] and nums[correctIndex]
int temp = nums[i];
nums[i] = nums[correctIndex];
nums[correctIndex] = temp;
} else {
i++;
// Find the missing number
for (i = 0; i < nums.length; i++) {
if (nums[i] != i) {
return i;
return nums.length;
6. Using Gauss’ Trick with Overflow Check
To prevent integer overflow in the sum formula method, we sum in chunks.
Code:
java
CopyEdit
public int missingNumber(int[] nums) {
long expectedSum = 0, actualSum = 0;
int n = nums.length;
for (int i = 0; i <= n; i++) {
expectedSum += i;
for (int num : nums) {
actualSum += num;
return (int) (expectedSum - actualSum);
}
Comparison of Methods
Method Time Complexity Space Complexity Notes
Summation Formula O(n) O(1) Might cause integer overflow
XOR Trick O(n) O(1) Efficient, avoids overflow issues
HashSet O(n) O(n) Extra space required
Sorting O(n log n) O(1) Slower than O(n) approaches
Cyclic Sort O(n) O(1) Good if modifying the array is allowed
