# Simple Java O(n) solution - HashSet

• Idea is to compute the sum mathematically first, and subtracting the elements from it.
Find the duplicate element, and add that to sum.

``````public int[] findErrorNums(int[] nums) {
Set<Integer> set = new HashSet<>();
int duplicate = 0, n = nums.length;
long sum = (n * (n+1)) / 2;
for(int i : nums) {
if(set.contains(i)) duplicate = i;
sum -= i;
}
return new int[] {duplicate, (int)sum + duplicate};
}``````

• What is the guarantee that sum + duplicate will always give the missing element?

• @lkjhgfdsa After subtracting all elements from expected 'sum', the value is nothing but (missing element - duplicate).
Here the guarantee is that only one duplicate exists, and only one missing element.

• What is the guarantee that sum + duplicate will always give the missing element?

@lkjhgfdsa There's only one missing element and one duplicate. So it'll be missing element.

• Nice solution, actually I have the same idea but I think it's not necessary to use hashset or hashmap.
Here is my code with cpp:

``````class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int dup = 0, N = nums.size();
vector<char> table(N + 1, 0);
long sum = (N * (N + 1)) / 2;
for (const auto &n : nums) {
if (++table[n] == 2)
dup = n;
sum -= n;
}
return{ dup, sum + dup };
}
};
``````

and another version without sum:

``````class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int dup = 0, N = nums.size();
vector<char> table(N + 1, 0);
for (const auto &n : nums)
if (++table[n] == 2)
dup = n;
for (int i = 0, j = N + 1;;) {
if (!table[++i]) return{ dup, i };
if (!table[--j]) return{ dup, j };
}
return{ 0, 0 };
}
};
``````

• ``````public int[] findErrorNums(int[] nums) {
int twice, miss;
int n = nums.length;
int[] hash = new int[n];
int sum = 0;
for(int num : nums){
hash[num-1]++;
if(hash[num-1] == 2) twice = num;
sum += num;
}
// The missing value is total - (sum - twice).
miss = n * (n+1)/2 - sum + twice;
return new int[]{twice, miss};
}
``````

• Actually we don't add i to set.

• Your method is very delicate.

• ``````public int[] findErrorNums(int[] nums) {
Set<Integer> set = new HashSet<>();
int n = nums.length;
int nSum = n*(n+1)/2;
int dup = 0, sumNoDup = 0;
for(int x: nums) {
if(set.contains(x)) dup = x;