Solving Missing Number

To see the question, click here.

Naive Approach

The idea is to sort the array and then compare the index with the number present at that index.

// TC: O(nlogn)
// SC: O(1)

import java.util.Arrays;

class MissingNumber {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return nums.length;
    }

    public static void main(String args[]) {
        MissingNumber mn = new MissingNumber();
        int[] nums = { 3, 0, 1 };
        System.out.println(mn.missingNumber(nums));
    }
}

Performance

The time complexity of the missingNumber method is O(nlogn) due to the sorting operation performed on the input array. The space complexity is O(1) because the algorithm uses a constant amount of extra space regardless of the size of the input array.

Refined Approach 1

Since the number range is [0,n], we can modify the cyclic sort algorithm to sort the array. We can then check if the number is the same as its index. If all numbers are in place, the missing number is the length of the array.

// TC: O(n)
// SC: O(1)

class MissingNumber {
    public int missingNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] < nums.length && nums[i] != nums[nums[i]]) {
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            } else {
                i++;
            }
        }

        for (i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }

        return nums.length;
    }

    public static void main(String args[]) {
        MissingNumber mn = new MissingNumber();
        int[] nums = { 3, 0, 1 };
        System.out.println(mn.missingNumber(nums));
    }
}

Performance

The time complexity of the missingNumber method is O(n). This is because we iterate through the array twice, once to swap elements and once to find the missing number. The space complexity is O(1) because we are not using any extra space that scales with the input size. We only use constant extra space for variables like i and temp.

Refined Approach 2

The idea is to calculate the sum of all the numbers in the array and return the difference of the sum up to n numbers and the array sum, which gives us the missing number.

// TC: O(n)
// SC: O(1)

class MissingNumber {
    public int missingNumber(int[] nums) {
        int arraySum = 0, n = nums.length;
        int sumToN = n * (n + 1) / 2;
        for (int i = 0; i < nums.length; i++) {
            arraySum += nums[i];
        }
        return sumToN - arraySum;
    }

    public static void main(String args[]) {
        MissingNumber mn = new MissingNumber();
        int[] nums = { 3, 0, 1 };
        System.out.println(mn.missingNumber(nums));
    }
}

Performance

The time complexity of the missingNumber method is O(n) because we iterate through the entire input array once to calculate the sum of all elements. The space complexity is O(1) because we only use a constant amount of extra space regardless of the size of the input array.

Efficient Approach

X^X = 0

X^0 = X

Since we are dealing with missing elements, let us try to solve using Bitwise XOR. When we perform an XOR operation on all the elements of the array with all the indices, the elements that are the same as their indices will cancel out. By XORing the result with the length of the array, we can find the element that is missing.

// TC: O(n)
// SC: O(1)

class MissingNumber {
    public int missingNumber(int[] nums) {
        int ans = nums.length;
        for (int i = 0; i < nums.length; i++) {
            ans = ans ^ i ^ nums[i];
        }
        return ans;
    }

    public static void main(String args[]) {
        MissingNumber mn = new MissingNumber();
        int[] nums = { 3, 0, 1 };
        System.out.println(mn.missingNumber(nums));
    }
}

Performance

The time complexity of the missingNumber method is O(n) because it iterates through the entire input array once. The space complexity is O(1) because the algorithm uses a constant amount of extra space regardless of the size of the input array.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.