- Problem Statement: Missing Number
- Simple Approach
- XOR Approach

Logicmojo - Updated Dec 12, 2023

You are given a list of n-1 integers, all of which are between 1 and n. The list contains no duplicates. In the list, one of the integers is missing. To find the missing integer, write an efficient code.

**Input:** list[] = {8, 3, 9, 6, 3, 7, 4,10,1}

**Output:** 5

**Explanation:** The missing number from 1 to 10 is 5.

**Input:** list[] = {2, 3, 5, 1}

**Output:** 4

**Explanation:** The missing number from 1 to 5 is 4.

We have presented two approaches to find the two elements:

** Simple Approach**

A simple solution is to simply scan the input array for every integer between 1 and n, halting the search as soon as a missing number is found. The time complexity of the input array will be O(n^2) because it is not sorted.

Can you do better than O(n^2)? Yes.

You could sort the array and then perform a linear scan O(n) to discover the missing number by comparing all successive elements. However, because of the time spent sorting, the temporal complexity of this approach is O(n log n).

You can do better. Here is a linear, O(n), solution that uses the arithmetic series sum formula.

sum(n)= n*(n+1)/2

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

#include <bits/stdc++.h> using namespace std; int getMissingNo(int a[], int n) { int total = (n + 1) * (n + 2) / 2; for (int i = 0; i < n; i++) total -= a[i]; return total; } int main() { int arr[] = { 1, 2, 4, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); int miss = getMissingNo(arr, n); cout << miss; }

import java.util.*; import java.util.Arrays; class Main{ public static int findMissingNumbers(int[] nums) { int n=nums.length; int sum=((n+1)*(n+2))/2; for(int i=0;i<n;i++) sum-=nums[i]; return sum; } public static void main(String[] args) { int[] a = { 1, 2, 4, 5, 6 }; System.out.println(findMissingNumbers(a)); } }

def getMissingNo(A): n = len(A) total = (n + 1)*(n + 2)/2 sum_of_A = sum(A) return total - sum_of_A A = [1, 2, 4, 5, 6] miss = getMissingNo(A) print(miss)

**Time Complexity**: O(n).

Only one traversal of the array is needed.

**Space Complexity**: O(1).

No extra space is needed

** XOR Approach**

We know that XOR of two equal numbers cancels each other. We can take advantage of this fact to find the missing number in the limited range array.

The idea is to compute XOR of all the elements in the array and compute XOR of all the elements from 1 to n+1, where n is the array’s size. Now the missing number would be the XOR between the two.

This approach is demonstrated below in C++, Java, and Python:

#include <bits/stdc++.h> using namespace std; int getMissingNo(int a[], int n) { int x1 = a[0]; int x2 = 1; for (int i = 1; i < n; i++) x1 = x1 ^ a[i]; for (int i = 2; i <= n + 1; i++) x2 = x2 ^ i; return (x1 ^ x2); } int main() { int arr[] = { 1, 2, 4, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); int miss = getMissingNo(arr, n); cout << miss; }

class Main { public static int getMissingNumber(int[] arr) { int xor = 0; for (int i: arr) { xor = xor ^ i; } for (int i = 1; i <= arr.length + 1; i++) { xor = xor ^ i; } return xor; } public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 7, 8, 9, 10 }; System.out.println("The missing number is " + getMissingNumber(arr)); } }

def getMissingNumber(arr): xor = 0 for i in arr: xor = xor ^ i for i in range(1, len(arr) + 2): xor = xor ^ i return xor if __name__ == '__main__': arr = [1, 2, 3, 4, 5, 7, 8, 9, 10] print('The missing number is', getMissingNumber(arr))

**Time Complexity**: O(n).

Only one traversal of the array is needed.

**Space Complexity**: O(1).

No extra space is needed