Algorithm
Problem Name: 268. Missing Number
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.length1 <= n <= 1040 <= nums[i] <= n- All the numbers of
numsare unique.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int missingNumber(int* nums, int numsSize) {
int i, k;
#if 0
k = numsSize;
for (i = 0; i < numsSize; i ++) {
k = k ^ i ^ nums[i];
}
#else
k = numsSize * (numsSize + 1) / 2;
for (i = 0; i < numsSize; i ++) {
k -= nums[i];
}
#endif
return k;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = 0, i = 0;
for(auto& x: nums) res ^= ++i ^ x;
return res;
}
};
class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum = 0, n = nums.size();
for (int& x: nums) {
sum += x;
}
return (1 + n) * n/2 - sum;
}
};
class Solution {
public:
int missingNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int l = 0, r = nums.size() - 1, mid;
while (l < = r) {
mid = l + (r - l)/2;
if (nums[mid] > mid) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int missingNumber(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
int n = nums.length;
int expectedSum = (n * (n + 1)) / 2;
return expectedSum - totalSum;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const missingNumber = function(nums) {
const n = nums.length
let xor = 0 ^ nums[0]
for(let i = 1; i < n; i++) xor = xor ^ i ^ nums[i]
return xor ^ n
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return len(nums)*(len(nums)+1)//2-sum(nums)
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0268_MissingNumber
{
public int MissingNumber(int[] nums)
{
int result = 0;
for (int i = 0; i < nums.Length; ++i)
result += (i + 1) - nums[i];
return result;
}
}
}
Input
Output