DEV Community

Aniket Vaishnav
Aniket Vaishnav

Posted on

Find Missing Number

Below is the one of the code using Xor

I've presented all the 5 techniques within the video description here

TL;DR
Description

Question

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Enter fullscreen mode Exit fullscreen mode
Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Enter fullscreen mode Exit fullscreen mode
Example 3:
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.
Enter fullscreen mode Exit fullscreen mode

All the numbers of nums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Solution

One of the approach is provided below

class Solution {
    /**
        x ^ 0 => x
        x ^ x => 0
     */
    public int missingNumber(int[] nums) {
        final int n = nums.length;
        // sum of n elements - sum of nums
        return xorOverRange(n) 
            ^ xorOverArray(nums);
    }

    int xorOverArray(int[] nums) {
        int xor = 0;
        for (int i = 0 ; i < nums.length; i++) {
            xor ^= nums[i];
        }
        return xor;
    }

    int xorOverRange(int n) {
        int xor = 0;
        for (int i = 0 ; i <= n; i++) {
            xor ^= i;
        }
        return xor;
    }
}
Enter fullscreen mode Exit fullscreen mode

For more different approach, checkout the video mentioned above.

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs