> ## Content Index
> Fetch the complete content index at: https://www.javahandbook.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# Solution Review: Missing Number
- URL: https://www.javahandbook.com/bitmask/solution-review-missing-number-2/
- Published: 2025-08-07T04:25:54.000Z
- Updated: 2025-08-07T04:25:54.000Z
- Description: 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.
- Author: Gopi Gorantala
- Tags: XOR Operator, #bitmask, #docs

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

```json
a ^ 0 = a

```

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

```json
a ^ a = 0
```

For `n` numbers, the math below can be applied.

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

```

For example:

```json
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

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

```py
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

```js
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++

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

```ts
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

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

```py
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

```js
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++

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

```ts
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.