How does The Interns Company match students with internships?

We use a combination of AI-powered matching algorithms and human expertise to connect students with internship opportunities that align with their skills, interests, and career goals.

Are the internship opportunities exclusive?

Yes, many of our partner companies offer positions exclusively through our platform that you won't find on public job boards or career sites.

Is there a cost to use The Interns Company?

Our basic matching service is free for students. Premium services like one-on-one interview coaching and resume reviews may have associated fees.

Missing Number

EasyAcceptance: 57.4%

Array Math Bit Manipulation

Problem Statement

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.

Constraints:

n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
All the numbers of nums are unique.

Input Format:

An array nums of n distinct numbers in the range [0, n]

Output Format:

Return the only number in the range [0, n] that is missing from the array

Examples:

Example 1:

Input:

nums = [3,0,1]

Output:

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:

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:

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.

Solutions

Math (Sum) Approach

Time: O(n)

Space: O(1)

Calculate the expected sum of numbers from 0 to n using the formula n*(n+1)/2, then subtract the actual sum of the array. The difference is the missing number.

Bit Manipulation (XOR) Approach

Time: O(n)

Space: O(1)

Use the XOR operation's property that a number XORed with itself is 0 and XOR is commutative and associative. XOR all numbers from 0 to n with all elements in the array. The result is the missing number.

Binary Search Approach

Time: O(n log n) due to sorting

Space: O(1) or O(n) depending on the sorting algorithm

Sort the array and perform binary search to find the missing number. If nums[mid] > mid, then the missing number is in the left half; otherwise, it's in the right half.

Algorithm Walkthrough

Example input: nums = [3,0,1]

Step-by-step execution:

Using the Sum approach with input [3, 0, 1]:
n = 3 (length of nums)
Expected sum = 3 * (3 + 1) / 2 = 6
Actual sum = 3 + 0 + 1 = 4
Missing number = 6 - 4 = 2
Alternatively, using the XOR approach:
Initialize result = 3 (length of nums)
For i=0: result = 3 ^ 0 ^ 3 = 0
For i=1: result = 0 ^ 1 ^ 0 = 1
For i=2: result = 1 ^ 2 ^ 1 = 2
Therefore, the missing number is 2.

Hints

Hint 1

Try to use the fact that the numbers are in range [0, n] and all but one number in this range is present.

Hint 2

Could you use the expected sum of numbers from 0 to n to find the missing number?

Hint 3

XOR operations have some interesting properties that could be useful here.

Hint 4

What happens when you XOR a number with itself? What about XOR with 0?

Video Tutorial

Missing Number - Multiple Approaches

YouTube•Learn the Missing Number solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the mathematical calculation or bit manipulation operations to find the missing number in the array.

Key visualization elements:

current index
expected value
actual value

Asked By

Amazon Microsoft Apple Google Facebook Bloomberg Adobe

Implementation Notes

This problem can be solved elegantly using mathematical properties or bit manipulation. The XOR approach is particularly clever as it has constant space complexity and linear time complexity without using any mathematical formula.