## 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]; return total; }

### 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) { ans.add(i + 1); } } return ans; }

### Python Implementation

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

**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.

### Dry Run of XoR Approach

### C Implementation of XoR Approach

int MissingNo(int arr[], int n) { int x1 = arr[0]; 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[0]; 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[0] 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

First Missing Integer

Repeat and Missing Number Array

## Frequently Asked 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.