# Find The Missing Number

## Problem Statement

You are given an array of integers of size N – 1 ranging from 1 to N. There are no duplicates in the list. One of the integers is missing in the array. The task is to find the missing number in the series.

Examples:

Input: list[] = {1, 2, 4, 6, 3, 7, 8,10,5}
Output: 9
Explanation: The missing number from 1 to 10 is 9.

Input: list[] = {3, 2, 4, 5}
Output: 3
Explanation: The missing number from 1 to 5 is 1.

## Simple Approach

This method uses the formula of summation.

The size of the array is N – 1. So the sum of n elements, that is the sum of numbers from 1 to N can be calculated by using the formula N * (N + 1) / 2. Now find the summation of all elements in the array and subtract it from the summation of first N natural numbers, the value obtained will be the value of the missing element.

Algorithm:

• Calculate the summation of first N natural numbers as Total = N * (N + 1) / 2
• Create a variable sum to store the summation of elements of the array.
• Iterate the array from start to end.
• Updating the value of sum as sum = sum + array[i]
• Print the missing number as the Total – sum

### C Implementation

```int MissingNo(int a[], int n) {
int i, total;
total = (n + 1) * (n + 2) / 2;
for (i = 0; i < n; i++)
total -= a[i];
}```

### Java Implementation

```MissingNumbers(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int index = Math.abs(arr[i]);
if (arr[index - 1] > 0) {
arr[index - 1] *= -1;
}
}
List < Integer > ans = new ArrayList < > ();
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
}
}
return ans;
}```

### Python Implementation

```def MissingNo(arr):
n = len(arr)
total = (n + 1)*(n + 2)/2
arr_sum = sum(arr)

Time Complexity: O(N) where N is the size of the array.
Space Complexity: O(1) because no extra space is needed.

## XoR Approach

This method uses the technique of XOR to solve the problem.

Approach: XOR has certain properties Assume
a1 ^ a2 ^ a3 ^ …^ an = A1 and a1 ^ a2 ^ a3 ^ …^ an-1 = A2, Then A1 ^ A2 = an

Algorithm:

• Create two variables a1= 0 and a2 = 0
• Iterate from 1 to n with i as the counter.
• For every index i update a1 as a1 = a1 ^ i
• Now iterate over the array from start to end.
• For every index i update a2 as a2 = a2 ^ arr[i]
• Print the missing number as a1 ^ a2.

### C Implementation of XoR Approach

```int MissingNo(int arr[], int n) {
int x1 = arr;
int x2 = 1;

for (int i = 1; i < n; i++)
x1 = x1 ^ arr[i];

for (int i = 2; i <= n + 1; i++)
x2 = x2 ^ i;

return (x1 ^ x2);
}```

### Java Implementation of XoR Approach

```static int MissingNo(int arr[], int n) {
int x1 = arr;
int x2 = 1;

for (int i = 1; i < n; i++)
x1 = x1 ^ arr[i];

for (int i = 2; i <= n + 1; i++)
x2 = x2 ^ i;

return (x1 ^ x2);
}```

### Python Implementation of XoR Approach

```def MissingNo(arr, n):
x1 = arr
x2 = 1

for i in range(1, n):
x1 = x1 ^ arr[i]

for i in range(2, n + 2):
x2 = x2 ^ i

return x1 ^ x2```

Time Complexity: O(N) where N is the size of the array because only one traversal is needed.
Space Complexity: O(1) because no extra space is needed.

## Practice Questions

What are the constraints of this problem?
All the numbers in the array should be between 1 to N, where N -1 is the size of the array.

Will these approaches work for larger numbers?
No, it will only work for numbers less than 10^6 because we can not make an array of greater size.

##### Previous Post ## Difference Between HTML and XHTML

##### Next Post 