Find missing number
Arrays
Logic Building
Easy
Given an integer array of size n containing distinct values in the range from 0 to n (inclusive), return the only number missing from the array within this range.
Examples:
Input: nums = [0, 2, 3, 1, 4]
Output: 5
Explanation: nums contains 0, 1, 2, 3, 4 thus leaving 5 as the only missing number in the range [0, 5]
Input: nums = [0, 1, 2, 4, 5, 6]
Output: 3
Explanation: nums contains 0, 1, 2, 4, 5, 6 thus leaving 3 as the only missing number in the range [0, 6]
Input: nums = [1, 3, 6, 4, 2, 5]
Constraints
- n == nums.length
- 1 <= n <= 104
- 0 <= nums[i] <= n
- All the numbers of nums are unique.
Hints
- "Use the formula for the sum of the first n natural numbers: S= (n×(n+1))/2. Subtract the sum of the array elements from S to find the missing number."
- Leverage the XOR property: x⊕x=0 and x⊕0=x. XOR all indices and array values; the missing number will be the result.
Company Tags
Rakuten
HCL Technologies
ARM
Rockstar Games
Roblox
PayPal
Robinhood
Snowflake
Philips Healthcare
Mastercard
Byju's
HashiCorp
Deloitte
NVIDIA
Texas Instruments
GE Healthcare
Freshworks
IBM
Lyft
Wayfair
Bloomberg
Teladoc Health
Chewy
Shopify
Salesforce
TCS
Cognizant
Accenture
Infosys
Capgemini
Wipro
Editorial
Intuition
For each number between 0 to N, try to find it in the given array using linear search. And if any number is not found, return that number.
Approach
i from 0 to N & for each integer i, try to find it in the given array using linear search.Solution
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the missing number
int missingNumber(vector<int>& nums) {
// Calculate N from the size of nums
int N = nums.size();
// Outer loop that runs from 0 to N
for (int i = 0; i <= N; i++) {
/* Flag variable to check
if an element exists*/
int flag = 0;
// Search for the element using linear search
for (int j = 0; j < N; j++) {
if (nums[j] == i) {
// i is present in the array
flag = 1;
break;
}
}
// Check if the element is missing (flag == 0)
if (flag == 0) return i;
}
/* The following line will never
execute,it is just to avoid warnings*/
return -1;
}
};
int main() {
vector<int> nums = {0,1, 2, 4};
// Create an instance of the Solution class
Solution solution;
/* Call the missingNumber method
to find the missing number*/
int ans = solution.missingNumber(nums);
cout << "The missing number is: " << ans << endl;
return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
import java.util.*;
class Solution {
// Function to find the missing number
public int missingNumber(int[] nums) {
// Calculate N from the length of nums
int N = nums.length;
// Outer loop that runs from 0 to N
for (int i = 0; i <= N; i++) {
/* Flag variable to check
if an element exists*/
int flag = 0;
/* Search for the element
using linear search*/
for (int j = 0; j < N; j++) {
if (nums[j] == i) {
// i is present in the array
flag = 1;
break;
}
}
// Check if the element is missing (flag == 0)
if (flag == 0) return i;
}
/* The following line will never
execute, it is just to avoid warnings*/
return -1;
}
}
public class Main {
public static void main(String[] args) {
// Example array with missing number
int[] nums = {0,1, 2, 4};
// Create an instance of the Solution class
Solution solution = new Solution();
// Call the missingNumber method to find the missing number
int ans = solution.missingNumber(nums);
// Output the missing number
System.out.println("The missing number is: " + ans);
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243
from typing import List
class Solution:
# Function to find the missing number
def missingNumber(self, nums: List[int]) -> int:
# Calculate N from the length of nums
N = len(nums)
# Outer loop that runs from 0 to N
for i in range(0, N+1):
""" Flag variable to check
if an element exists"""
flag = 0
""" Search for the element
using linear search"""
for num in nums:
if num == i:
# i is present in the array
flag = 1
break
""" Check if the element
is missing (flag == 0)"""
if flag == 0:
return i
""" The following line will never
execute, it is just to avoid warnings"""
return -1
# Main function to test the implementation
if __name__ == "__main__":
nums = [0,1, 2, 4]
# Create an instance of the Solution class
solution = Solution()
# Call the missingNumber method to find the missing number
ans = solution.missingNumber(nums)
print(f"The missing number is: {ans}")
1234567891011121314151617181920212223242526272829303132333435363738394041
class Solution {
// Function to find the missing number
missingNumber(nums) {
// Calculate N from the size of nums
const N = nums.length;
// Outer loop that runs from 0 to N
for (let i = 0; i <= N; i++) {
/* Flag variable to check
if an element exists*/
let flag = 0;
// Search for the element using linear search
for (let j = 0; j < N; j++) {
if (nums[j] === i) {
// i is present in the array
flag = 1;
break;
}
}
// Check if the element is missing (flag == 0)
if (flag === 0) return i;
}
/* The following line will never
execute, it is just to avoid warnings*/
return -1;
}
}
const nums = [0, 1, 2, 4];
// Create an instance of the Solution class
const solution = new Solution();
/* Call the missingNumber method
to find the missing number */
const ans = solution.missingNumber(nums);
console.log("The missing number is: " + ans);Complexity Analysis
Time Complexity: O(N^2), where N is the size of the array. In the worst case i.e. if the missing number is N itself, the outer loop will run for N times, and for every single number the inner loop will also run for approximately N times. So, the total time complexity will be O(N^2).Space Complexity: O(1) , as no extra space is used.
Intuition
The better idea rather than linear search is to use the hashing technique by storing the frequency of each element of the given array. Any number whose frequency will be 0, will be returned as that will correspond to the missing value.
Approach
Solution
123456789101112131415161718192021222324252627282930313233343536373839404142434445
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the missing number
int missingNumber(vector<int>& nums) {
int N = nums.size();
// Array to store frequencies, initialized to 0
int freq[N+1] = {0};
// Storing the frequencies in the array
for (int num : nums) {
freq[num]++;
}
// Checking the frequencies for numbers 0 to N
for (int i = 0; i <= N; i++) {
if (freq[i] == 0) {
return i;
}
}
/* This line will never execute,
it is just to avoid warnings*/
return -1;
}
};
int main() {
vector<int> nums = {0,1, 2, 4};
// Create an instance of the Solution class
Solution solution;
/* Call the missingNumber method
to find the missing number*/
int ans = solution.missingNumber(nums);
cout << "The missing number is: " << ans << endl;
return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243
import java.util.Arrays;
class Solution {
// Function to find the missing number
public int missingNumber(int[] nums) {
int N = nums.length;
// Array to store frequencies, initialized to 0
int[] freq = new int[N+1];
// Storing the frequencies in the array
for (int num : nums) {
freq[num]++;
}
// Checking the frequencies for numbers 0 to N
for (int i = 0; i <= N; i++) {
if (freq[i] == 0) {
return i;
}
}
/* This line will never execute,
it is just to avoid warnings */
return -1;
}
}
public class Main {
public static void main(String[] args) {
int[] nums = {0,1, 2, 4};
// Create an instance of the Solution class
Solution solution = new Solution();
/* Call the missingNumber method
to find the missing number */
int ans = solution.missingNumber(nums);
System.out.println("The missing number is: " + ans);
}
}
123456789101112131415161718192021222324252627282930313233343536
from typing import List
class Solution:
# Function to find the missing number
def missingNumber(self, nums: List[int]) -> int:
N = len(nums)
# Array to store frequencies, initialized to 0
freq = [0] * (N + 1)
# Storing the frequencies in the array
for num in nums:
freq[num] += 1
# Checking the frequencies for numbers 0 to N
for i in range(0, N + 1):
if freq[i] == 0:
return i
""" This line will never execute,
it is just to avoid warnings"""
return -1
# Main function to test the implementation
if __name__ == "__main__":
nums = [0,1, 2, 4]
# Create an instance of the Solution class
solution = Solution()
""" Call the missingNumber method
to find the missing number"""
ans = solution.missingNumber(nums)
print(f"The missing number is: {ans}")
1234567891011121314151617181920212223242526272829303132333435363738394041424344
class Solution {
// Function to find the missing number
missingNumber(nums) {
const N = nums.length;
// Array to store frequencies, initialized to 0
const freq = new Array(N + 1).fill(0);
// Storing the frequencies in the array
for (let num of nums) {
freq[num]++;
}
// Checking the frequencies for numbers 1 to N
for (let i = 0; i <= N; i++) {
if (freq[i] === 0) {
return i;
}
}
/* This line will never execute,
it is just to avoid warnings */
return -1;
}
}
// Main function to test the implementation
const main = () => {
const nums = [0,1, 2, 4];
// Create an instance of the Solution class
const solution = new Solution();
/* Call the missingNumber method
to find the missing number*/
const ans = solution.missingNumber(nums);
// Output the missing number
console.log(`The missing number is: ${ans}`);
};
// Call the main function
main();
Complexity Analysis
Time Complexity: O(N) + O(N) ~ O(2N), where N is size of the array + 1. For storing the frequencies in the hash array, the program takes O(N) time complexity and for checking the frequencies in the second step again O(N) is required. So, the total time complexity is O(N) + O(N)Space Complexity: O(N) where N is size of the array + 1, as extra hash space is used.
Intuition
The optimal is based on simple mathematics, where addition and summation of series is involved.
Ideally while solving this problem, if you think of calculating the sum of natural numbers from 0 to N and also compute the sum of all elements in the array separately. Then, just by subtracting the two results, we can easily identify the missing number. This missing number would not have been included in the sum of all elements of the given array.
Approach
sum1
sum2
sum1and sum2, return it.Dry Run
Solution
12345678910111213141516171819202122232425262728293031323334353637383940414243
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the missing number
int missingNumber(vector<int>& nums) {
// Calculate N from the size of nums
int N = nums.size();
// Summation of first N natural numbers
int sum1 = (N * (N + 1)) / 2;
// Summation of all elements in nums
int sum2 = 0;
for (int num : nums) {
sum2 += num;
}
// Calculate the missing number
int missingNum = sum1 - sum2;
// Return the missing number
return missingNum;
}
};
int main() {
// Example vector with missing number
vector<int> nums = {0,1, 2, 4};
// Create an instance of the Solution class
Solution solution;
/* Call the missingNumber method
to find the missing number*/
int ans = solution.missingNumber(nums);
cout << "The missing number is: " << ans << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839
import java.util.*;
class Solution {
// Function to find the missing number
public int missingNumber(int[] nums) {
// Calculate N from the length of nums
int N = nums.length;
// Summation of first N natural numbers
int sum1 = (N * (N + 1)) / 2;
// Summation of all elements in nums
int sum2 = 0;
for (int num : nums) {
sum2 += num;
}
// Calculate the missing number
int missingNum = sum1 - sum2;
// Return the missing number
return missingNum;
}
public static void main(String[] args) {
// Example array with missing number
int[] nums = {0,1, 2, 4};
// Create an instance of the Solution class
Solution solution = new Solution();
/* Call the missingNumber method
to find the missing number*/
int ans = solution.missingNumber(nums);
System.out.println("The missing number is: " + ans);
}
}
123456789101112131415161718192021222324252627282930313233
from typing import List
class Solution:
# Function to find the missing number
def missingNumber(self, nums: List[int]) -> int:
# Calculate N from the length of nums
N = len(nums)
# Summation of first N natural numbers
sum1 = (N * (N + 1)) // 2
# Summation of all elements in nums
sum2 = sum(nums)
# Calculate the missing number
missingNum = sum1 - sum2
# Return the missing number
return missingNum
if __name__ == "__main__":
# Example list with missing number
nums = [0,1, 2, 4]
# Create an instance of the Solution class
solution = Solution()
""" Call the missingNumber method
to find the missing number"""
ans = solution.missingNumber(nums)
print("The missing number is: ",ans)
123456789101112131415161718192021222324252627282930313233343536373839
class Solution {
// Function to find the missing number
missingNumber(nums) {
// Calculate N from the length of nums
let N = nums.length;
// Summation of first N natural numbers
let sum1 = (N * (N + 1)) / 2;
// Summation of all elements in nums
let sum2 = nums.reduce((acc, num) => acc + num, 0);
// Calculate the missing number
let missingNum = sum1 - sum2;
// Return the missing number
return missingNum;
}
}
// Main function to test the implementation
const main = () => {
// Example array with missing number
const nums = [0,1, 2, 4];
// Create an instance of the Solution class
const solution = new Solution();
/* Call the missingNumber method
to find the missing number*/
const ans = solution.missingNumber(nums);
// Output the missing number
console.log(`The missing number is: ${ans}`);
};
// Call the main function
main();
Complexity Analysis
Time Complexity: O(N) where N is size of array, to compute the sum of the array elements. Space Complexity: O(1) as no extra space is used.Intuition
Another optimal approach, uses the below property of XOR to find the missing number.
Understand that on calculating the XOR of all numbers from 1 to N we make sure that each number is included. After that on calculating the XOR of all the elements in the array & then performing XOR these two results, all the numbers present in the final result will appear twice expect for the one which is missing. Hence the number occurring twice turn out 0 satisfying first condition, and then followed by 0 ^ missing number, leaving the missing number itself.
Approach
xor1, xor2 as 0. xor1 variable will calculate the XOR of 1 to NDry Run
Solution
12345678910111213141516171819202122232425262728293031323334353637
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the missing number
int missingNumber(vector<int>& nums) {
int xor1 = 0, xor2 = 0;
// Calculate XOR of all array elements
for (int i = 0; i < nums.size(); i++) {
xor1 = xor1 ^ (i + 1); //XOR up to [1...N]
xor2 = xor2 ^ nums[i]; // XOR of array elements
}
// XOR of xor1 and xor2 gives missing number
return (xor1 ^ xor2);
}
};
int main() {
vector<int> nums = {1, 2, 4, 0};
// Create an instance of the Solution class
Solution solution;
/* Call the missingNumber method
to find the missing number*/
int ans = solution.missingNumber(nums);
cout << "The missing number is: " << ans << endl;
return 0;
}
12345678910111213141516171819202122232425262728293031
import java.util.*;
class Solution {
// Function to find missing number in array
public int missingNumber(int[] nums) {
int xor1 = 0, xor2 = 0;
// Calculate XOR of all array elements
for (int i = 0; i < nums.length; i++) {
xor1 = xor1 ^ (i + 1); // XOR up to [1...N]
xor2 = xor2 ^ nums[i]; // XOR of array elements
}
// XOR of xor1 and xor2 gives missing number
return (xor1 ^ xor2);
}
public static void main(String[] args) {
int[] nums = {1, 2, 4, 0};
// Create an instance of the Solution class
Solution solution = new Solution();
/* Call the missingNumber method
to find the missing number*/
int ans = solution.missingNumber(nums);
System.out.println("The missing number is: " + ans);
}
}
12345678910111213141516171819202122232425262728293031
from typing import List
class Solution:
# Function to find the missing number
def missingNumber(self, nums: List[int]) -> int:
xor1 = 0
xor2 = 0
# Calculate XOR of all array elements
for i in range(len(nums)):
xor1 ^= (i + 1) # XOR up to [1...N]
xor2 ^= nums[i] # XOR of array elements
# XOR of xor1 and xor2 gives missing number
return xor1 ^ xor2
# Main function to test the implementation
if __name__ == "__main__":
nums = [1, 2, 4, 0]
# Create an instance of the Solution class
solution = Solution()
""" Call the missingNumber method
to find the missing number"""
ans = solution.missingNumber(nums)
print(f"The missing number is: {ans}")
123456789101112131415161718192021222324252627282930313233343536
class Solution {
// Function to find the missing number
missingNumber(nums) {
let xor1 = 0;
let xor2 = 0;
// Calculate XOR of all array elements
for (let i = 0; i < nums.length ; i++) {
xor1 ^= (i + 1); // XOR up to [1...N]
xor2 ^= nums[i]; // XOR of array elements
}
// XOR of xor1 and xor2 gives missing number
return xor1 ^ xor2;
}
}
// Main function to test the implementation
const main = () => {
const nums = [1, 2, 4, 0];
// Create an instance of the Solution class
const solution = new Solution();
/* Call the missingNumber method
to find the missing number*/
const ans = solution.missingNumber(nums);
console.log(`The missing number is: ${ans}`);
};
// Call the main function
main();
Complexity Analysis
Time Complexity: O(N) for getting the sum of the array elements, where N is the size of the array. Space Complexity: O(1) as no extra space is used.Frequently Occurring Doubts
Q: Why use the sum formula instead of iterative checks?
A: The sum formula is faster (O(n)) compared to iterative checks (O(n2)) because the sum formula requires only a single pass to compute the sum of array elements and one subtraction. Iterative checks require comparing each number in the range to the array, which is inefficient.
Q: What happens if the missing number is 0 or n?
A: If 0 is missing, the sum formula still works because S includes 0 by definition. If n is missing, the sum formula accounts for n since it calculates the sum of the entire range, and subtracting the array sum leaves n
Interview Followup Questions
Q: How would you handle the problem if duplicates are allowed in the array?
A: If duplicates are allowed: Use a hash set to track numbers present in the array. Iterate through 0 to n, checking if each number exists in the set. This approach requires O(n) time and O(n) space.
Q: How does the performance compare between the sum formula and XOR methods?
A: Both methods have O(n) time complexity and O(1) space complexity. The sum formula involves addition and subtraction, while the XOR method uses bitwise operations. XOR is slightly faster in practice due to the lower computational cost of bitwise operations.
Notes
Code
✅ Testcase
Input: {'nums': '[0, 2, 3, 1, 4]'}
Expected:
5
5
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[0, 1, 2, 4, 5, 6]'}
Expected:
3
3
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[1, 3, 6, 4, 2, 5]'}
Expected:
0
0
Actual: -
Time: -
sec
Status: Waiting
Facts
- • Fun Fact: The problem concept of identifying missing elements in a sequence is commonly used in the software industry for a variety of purposes
- • For instance, it’s integral in database management where checking for missing IDs or sequence gaps is crucial
- • The concept is also highly relevant in network programming, specifically in TCP (Transmission Control Protocol) where packet sequence numbers are maintained
- • Identifying missing sequence numbers helps in detecting packet loss during data transmission