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

## 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

1. Initialize a variable, `result = 0`.
2. 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.

Coding Interview QuestionsData Structures and AlgorithmsArraysBit Manipulation

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

## Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!