# Solution Review: Missing Number

We solved the problem using lookup (hashtable), using the mathematical formula. Let's solve this more efficiently using bit-level operations with XOR and then optimize the solution.

## Table of Contents

## Introduction

We solved the problem using lookup (hashtable) and using the mathematical formula for the sum of n natural numbers. Let's solve this more efficiently using bit-level operations with XOR.

I hope you had a chance to solve the above challenge.

Let us see the solution in detail.

We solved the problem using lookup (Memoization/Hashtable) and using the mathematical formula for the sum of n natural numbers, Let's solve this more efficiently using bit-level operations with`^`

or`xor`

.

## Bit manipulation approach

We are dealing with bit manipulation and want to solve these problems with Bitwise operators.

## Concepts

If we take XOR of `0`

and a `bit`

, it will return that `bit`

.

```
a ^ 0 = a
```

If we take the XOR of two same bits, it will return `0`

.

`a ^ a = 0`

For `n`

numbers, the math below can be applied.

```
a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b;
```

For example:

`1 ^ 5 ^ 1 = (1 ^ 1) ^ 5 = 0 ^ 5 = 5;`

Did that clue you?

As per our above analysis, we can `xor`

combine elements to find the missing number.

## Algorithm

- Initialize a variable,
`result = 0`

. - Iterate over array elements from
`0`

to`length + 1`

and do`^`

of each with the above-initialized variable.

## Solution

The final solution looks like this:

### Java

```
class MissingNumber {
private static int helper(int[] nums) {
int n = nums.length + 1;
int res = 0;
for (int i = 0; i < n; i++) {
res ^= i;
}
for (int value : nums) {
res ^= value;
}
return res;
}
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 getMissingNumber(nums):
res = 0
for i in nums:
res ^= i
for i in range(0, len(nums) + 1):
res = res ^ i
return res
nums = [9,6,3,5,4,2,1,0,7]
print("The missing number is", getMissingNumber(nums))
```

### JavaScript

```
const MissingNumber = array => {
function helper (nums) {
const n = nums.length + 1;
let res = 0;
for(let i = 0; i < n; i++) {
res ^= i;
}
for(const value of nums) {
res ^= value;
}
return res;
}
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(int arr[], int n) {
int res = 0;
for (int i = 0; i < n; i++) {
res ^= arr[i];
}
for (int i = 0; i <= n; i++) {
res ^= i;
}
return res;
}
int main() {
int arr[] = {9, 6, 4, 2, 3, 5, 7, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Missing element in the array is " << getMissingNumber(arr, n);
return 0;
}
```

### TypeScript

```
export const MissingNumber = (array: number[]): number => {
function helper(nums: number[]): number {
const n: number = nums.length + 1;
let res: number = 0;
for (let i = 0; i < n; i++) {
res ^= i;
}
for (const value of nums) {
res ^= value;
}
return res;
}
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)`

We are using two independent loops. So time = `O(n) + O(n)`

=> `2*O(n)`

, which is `O(n)`

.

Where, `n`

is the number of elements in the array since we must iterate over all the elements to find a missing number. So, the best and the worst-case time is `O(n)`

.

**Space complexity:** `O(1)`

. The space complexity is `O(1)`

. No extra space is allocated.

## Optimization

Can we further optimize the algorithm? Yes, we can reduce running two `for-loops`

to one, and still, the algorithm runs in linear time. 🤩

Let us optimize the final solution. We are using two independent for loops to find the missing number. Now, let’s make it a single for loop.

We do two million operations if we have an array of one million integers. We can reduce the number of operations into `n`

, where `n`

is the array’s size.

Here the code has fewer lines compared to the one above. Let’s look at the below code:

### Java

```
class MissingNumber {
private static int helper(int[] nums) {
int missing = nums.length;
for (int i = 0; i < nums.length; i++) {
missing ^= i ^ nums[i];
}
return missing;
}
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 MissingNumber(nums):
missing=len(nums)
for i in range(0,len(nums)):
missing ^= i ^ nums[i]
return missing
nums=[9,6,4,2,3,5,7,0,1]
print("Missing element in the array is: ",MissingNumber(nums))
```

### JavaScript

```
const MissingNumber = array => {
function helper (nums) {
let missing = nums.length;
for(let i = 0; i < nums.length; i++) {
missing ^= i ^ nums[i];
}
return missing;
}
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 helper(int arr[], int n) {
int m = n;
for (int i = 0; i < n; i++)
m ^= i ^ arr[i];
return m;
}
int main() {
int arr[] = {9, 6, 4, 2, 3, 5, 7, 0, 1};
int n = 9;
cout << "missing element is : " << helper(arr, n);
return 0;
}
```

### TypeScript

```
export const MissingNumber = (array: number[]): number => {
function helper(nums: number[]): number {
let missing: number = nums.length;
for (let i = 0; i < nums.length; i++) {
missing ^= i ^ nums[i];
}
return missing;
}
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)`

: Where, `n`

is the number of elements in the array, as we must iterate over all the elements to find a missing number. So, the best, worst-case time is `O(N)`

.

**Space complexity:** `O(1)`

The space complexity is O(1), and no extra space is allocated.

Finding a missing number in an array of numbers will be easy using the bit manipulation approach that takes no extra space and runs linearly.

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.