268. Missing Number

• Link: https://leetcode.com/problems/missing-number/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.

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.

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.

Constraints:

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• 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?

Approach 1: Brute Force

Intuition

• Loop through numbers from 0 to n and check if each number is in nums.
• Linear Search DSA

Algorithm

1. Loop from 0 to n using for loop i
   1. Nest another loop to linear search i in nums
      1. If not present return i
2. return n

Code

class Solution {
public:
	int missingNumber(vector<int>& nums) {

		for (int i = 0; i < nums.size() ; i++) {

			bool isPresent = false;

			for (int num: nums) {
				if (num == i) {
					isPresent = true;
					break;
				}
			}

			if (!isPresent) return i;

		}

		return nums.size();
	}
};

Complexity Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$

Approach 2: Better

Intuition

• Hashing

Algorithm

1. Declare a vector hash of length n+1 & initialize it with 0
2. Iterate through each element of nums & hash[nums[i]] = 1
3. Loop through each element of hash (i.e; 0 to n) if hash[i] == 0 return i;
4. Or return -1;

Code

class Solution {
public:
	int missingNumber(vector<int>& nums) {
		int n = nums.size();
		vector<int> hash(n+1, 0);
		
		for (int num : nums) {
			hash[num] = 1;
		}
		
		for (int i = 0 ; i < n + 1 ; i++) {
			if (hash[i] == 0) return i;
		}
		
		return -1;
	}
};

Complexity Analysis

• Time Complexity: $O(n+n+1)=O(n)$
• Space Complexity: $O(n+1)=O(n)$

Approach 3: Optimal

Intuition

• Math Formula, sum of n natural numbers

Algorithm

1. Declare & initialize n = nums.size()
2. Calculate the expected sum of n numbers
3. Calculate the actual sum by looping through the nums array
4. Return the difference of actual & expected sum

Code

class Solution {
public:
	int missingNumber(vector<int>& nums) {
		int n = nums.size();
		int expectedSum = n*(n+1) / 2;
		int actualSum = 0;
		for (int num: nums) {
			actualSum += num;
		}
		return expectedSum - actualSum;
	}
};

Complexity Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Approach 4: Optimal 2

Intuition

• Bit Manipulation DSA XOR (^)

• 2^2 = 0

• 3^3 = 0

• 2^2^3^3 = 0

• 2^0 = 2

• 0^3 = 3

• Advantage over sum formula?

  • if n is larger the expected sum can overflow int datatype

Algorithm

1. Declare & initialize n = nums.size()
2. Declare int xor1 = 0
3. Loop from 0 to n with int i
   1. xor1 = xor1 ^ i
4. Declare int xor2 = 0
5. Loop through nums
   1. xor2 = xor2 ^ nums[i]
6. Return xor1 ^ xor2

Code

class Solution {
public:
	int missingNumber(vector<int>& nums) {
		int n = nums.size();

		int xor1 = 0;
		for (int i = 0 ; i < n+1 ; i++) {
			xor1 = xor1 ^ i;
		}
		
		int xor2 = 0;
		for (int i = 0 ; i < n ; i++) {
			xor2 = xor2 ^ nums[i];
		}
		
		return xor1 ^ xor2;
	}
};

Complexity Analysis

• Time Complexity: $O(2n)=O(n)$
• Space Complexity: $O(1)$