Daily Dose of DSA - Day 8
Missing number using unordered map (O(n)TC O(n)SC), using Bitwise XOR (O(n)TC O(1)SC) and sum method (O(n)TC O(1)SC)
Table of contents
No headings in the article.
class Solution
{
public:
int missingNumber(vector<int> &nums) //
{
int ans = 0;
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i++)
m[nums[i]]++;
for (int i = 0; i <= nums.size(); i++)
{
if (!(m.find(i) != m.end()))
// if(m.count(i)==0)
{
ans = i;
}
}
return ans;
}
};
//In the XOR method we take bitwise XOR of indexes and the number, if indexes and number are present in the process their effect gets cancelled and the extra element is remained .
class Solution
{
public:
int missingNumber(vector<int> &nums)
{
int n = nums.size();
int x = 0;
for (int i = 0; i < n; i++) //
{
x ^= i;
x ^= nums[i];
}
x ^= n;
return x;
}
};
class Solution
{
public:
int missingNumber(vector<int> &nums)
{
int n = nums.size();
int x = (n * (n + 1)) / 2;
int y = 0;
for (int i = 0; i < n; i++)
{
y = y + nums[i];
}
return x - y;
}
};