# Find The Missing Number From The Array

In this article, we'll learn various ways to find the missing number in an array. We use a memoization approach, a mathematical approach, and the most optimized way using the XOR operator.

In this lesson, we use XOR principles to find a missing element.

## Introduction

We make use of XOR principles in finding a missing element.

Let’s see how to achieve this using the XOR operator.

## Problem statement

Given an array of `nums` containing `n` distinct numbers in the range `[0, N]`, return the only number in the range that is missing from the array.

``````Input: nums = { 9, 6, 4, 2, 3, 5, 7, 0, 1 }

Output: 8

Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.``````

Constraints:

``````1. It should run in linear time.
2. n equals to nums array length.``````
Hint: Use arithmetic progression, and go with the brute force approach. You can optimize the code later with a better version.

## Intuition

There are different ways to solve this problem.

1. Memoization/Hashtable approach.
2. Math/Summation approach

## Memoization/Hashtable approach

In this approach, we use a hashtable data structure to store all the unique elements, and we run a `for-loop` from `0` to `nums.length + 1` which gives us the window to find the missing element.

### Algorithm

This algorithm is almost identical to the Brute force approach, except we first insert each element of `nums` into a `Set`, allowing us to later query for containment in `O(1)` time.

### Solutions

#### Java

``````import java.util.HashSet;

class MissingNumber {
private static int helper(int[] nums) {
HashSet<Integer> set = new HashSet<Integer>();

for (int num : nums) {
}

int n = nums.length + 1;

for (int i = 0; i < n; i++) {
if (!set.contains(i)) {
return i;
}
}
return -1;
}

public static void main(String[] args) {
int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
System.out.println("Missing element in the array is " + helper(nums));
}
}``````

#### Python:

``````def missing_number(array):
num_set = set()

for num in array:

n = len(array) + 1

for i in range(n):
if i not in num_set:
return i

return -1

array = [9, 6, 4, 2, 3, 5, 7, 0, 1]
print("Missing element in the array is", missing_number(array))
``````

#### JavaScript:

``````const MissingNumber = array => {

function helper (nums) {
const set = new Set (); // we can use js object, `const lookup = {}`

for(let i = 0; i < nums.length; i++) {
}

let n = nums.length + 1;

for(let i = 0; i < n; i++) {
if(!set.has (i)) {
return i;
}
}
return -1;
}

return helper (array);
}

const array = [9, 6, 4, 2, 3, 5, 7, 0, 1];
console.log (`Missing element in the array is \${MissingNumber (array)}`);
``````

#### C++:

``````#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
int arr[] = {9, 6, 4, 2, 3, 5, 7, 0, 1};
int n = 9;
unordered_map<int, bool> numberMap;
for (int i : arr) {
if (numberMap.find(i) == numberMap.end()) {
numberMap[i] = true;
} else {
cout << "repeating" << i;
}
}
cout << endl;
for (int i = 1; i <= n; i++) {
if (numberMap.find(i) == numberMap.end()) {
cout << "Missing element in the array is: " << i;
}
}
return 0;
}
``````

#### TypeScript:

``````export const MissingNumber = (array: number[]): number => {
function helper(nums: number[]): number {
// we can use js object, `const lookup = {}`
const set = new Set();

for (let i = 0; i < nums.length; i++) {
}

let n: number = nums.length + 1;

for (let i = 0; i < n; i++) {
if (!set.has(i)) {
return i;
}
}
return -1;
}

return helper(array);
}

const array: number[] = [9, 6, 4, 2, 3, 5, 7, 0, 1];
console.log(`Missing element in the array is \${MissingNumber(array)}`);
``````

### Complexity Analysis

Time complexity: `O(n)`The time complexity of for loops is `O(n)` and the time complexity of the hash table operation added is `O(1)`.

Space complexity: `O(n)`The space required by the hash table is equal to the number of elements in `nums`.

## Summation (Maths) approach

This uses concepts regarding `n` natural numbers.

### Algorithm

1. We know the sum of `n` natural numbers are `[n(n+1)/2]`.
2. The difference between the actual sum of the given array of elements and the sum of `n` natural numbers give us the missing number.

### Solutions

#### Java:

``````class MissingNumber {
private static int helper(int[] nums) {
int n = nums.length;
int expectedSum = ((n * (n + 1)) / 2);

int actualSum = 0;

for (int num : nums) {
actualSum += num;
}

return expectedSum - actualSum;
}

public static void main(String[] args) {
int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
System.out.println("Missing element in the array is " + helper(nums));
}
}``````

#### Python:

``````def helper(nums):
n = len(nums)
expected_sum = n * (n + 1) // 2

actual_sum = 0

for num in nums:
actual_sum += num

return expected_sum - actual_sum

nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
print("Missing element in the array is", helper(nums))``````

#### JavaScript:

``````const MissingNumber = array => {

function helper (nums) {
const n = nums.length;
const expectedSum = ((n * (n + 1)) / 2);

let actualSum = 0;

for(let num of nums) {
actualSum += num;
}

return expectedSum - actualSum;
}

return helper (array);
}

const array = [9, 6, 4, 2, 3, 5, 7, 0, 1];
console.log (`Missing element in the array is \${MissingNumber (array)}`);
``````

#### C++:

``````#include <iostream>

using namespace std;

int getMissingNumber(const int arr[], int n) {
int m = n + 1;
int total = m * (m + 1) / 2;

int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}

}

int main() {
int arr[] = {9, 6, 4, 2, 3, 5, 7, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Missing element in the array is %d", getMissingNumber(arr, n));
return 0;
}
``````

#### TypeScript:

``````export const MissingNumber = (array: number[]): number => {
function helper(nums: number[]): number {
const n: number = nums.length;
const expectedSum: number = ((n * (n + 1)) / 2);

let actualSum: number = 0;

for (let num of nums) {
actualSum += num;
}

return expectedSum - actualSum;
}

return helper(array);
}

const array: number[] = [9, 6, 4, 2, 3, 5, 7, 0, 1];
console.log(`Missing element in the array is \${MissingNumber(array)}`);
``````

### Complexity Analysis

Time complexity: `O(n)`The time complexity of the for loop is `O(n)`.

Space complexity: `O(1)`, as we are not using any extra space.

## Coding exercise

First, look at these code snippets above and think of a solution.

Your solution must use the `^` operator.

This problem is designed for your practice, so try to solve it yourself first. If you get stuck, you can always refer to the solution provided in the solution section. Good luck!

Hint: Use XOR techniques you learned in previous lessons and try to come up with an algorithm.
``````// java
// TODO: finish the challenge or check next lesson for solution
class Solution{
public static int missingNumber(int[] nums){
// Write - Your - Code- Here

return -1; // change this, return missing element; if none, return -1
}
}``````
``````# Python
# TODO: finish the challenge or check next lesson for solution
def missingNumber(nums):
# Write - Your - Code- Here

return -1 # change this, return missing element; if none, return -1``````
``````// javascript
// TODO: finish the challenge or check next lesson for solution
const MissingNumber = array => {
// Write - Your - Code- Here

return -1; // change this, return missing element; if none, return -1
}``````
``````// c++
// TODO: finish the challenge or check next lesson for solution
#include <iostream>
using namespace std;

int countSetBits(int array[]) {
// Write - Your - Code- Here

return -1; // change this and return the correct setbit count
}``````
``````// c++
// TODO: finish the challenge or check next lesson for solution
export const MissingNumber = (array: number[]): number => {
// Write - Your - Code- Here

return -1; // change this, return missing element; if none, return -1
}``````

The solution will be explained in the next lesson.

Coding Interview QuestionsData Structures and AlgorithmsBit Manipulation

### Gopi Gorantala Twitter

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things