Challenge 1: Missing Number

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) {
            set.add(num);
        }

        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:
        num_set.add(num)

    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++) {
            set.add (nums[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++) {
            set.add(nums[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];
    }

    return total - sum;
}

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.