Problem
DailyCoding
You are given an array of positive numbers from 1 to n, such that all numbers from 1 to n are present except one number x. You have to find x. The input array is not sorted.
[3,7,1,2,8,4,5] n = 8 missing number = 6
Leetcode
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.
Solution
Any solution will be at least O(n) because we need to examine all numbers to find the missing one.
Sorting - O(n) time - O(1) space
class Solution {
int findMissing(vector<int> numbers) {
sort(numbers.begin(), numbers.end());
for (int i = 0; i < numbers.size(); i++) {
if (numbers[i] != i+1) return i+1;
}
return -1;
}
}class Solution {
public:
int missingNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
if(nums[0] != 0) return 0;
if(nums[n-1] != n) return n;
for(int i = 1; i < nums.size(); i++) {
if(nums[i] != i) return i;
}
return 0;
}
};Missing Sum - O(n) time - O(1) space
class Solution {
int findMissing(vector<int> numbers) {
int correctSum = 0;
int currentSum;
for (int i = 1; i <= numbers.size(); i++) correctSum++;
for (int i = 0; i < numbers.size(); i++) currentSum += numbers[i];
int answer = correctSum - currentSum;
return answer >= 0 ? answer : -1;
}
}class Solution {
public:
int missingNumber(vector<int>& nums) {
int correctSum = 0;
int vectorSum = accumulate(nums.begin(), nums.end(), 0);
for (int i = 1; i <= nums.size(); i++) correctSum += i;
return correctSum - vectorSum;
}
};Bitwise XOR - O(n) time - O(1) space
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int ans = 0;
for(int i = 1; i <= n; i++) ans = ans ^ i;
for(int i = 0; i < nums.size(); i++) ans= ans^nums[i];
return ans;
}
};