Two Sum Unique Pairs Solution Amazon OA 2022

Page Contents

Two Sum Unique Pairs Solution

Write a function that takes a list of numbers and a target number, and then returns the number of unique pairs that add up to the target number. [X, Y] and [Y, X] are considered the same pair, and not unique.

Examples

Example 1:

Input: [1, 1, 2, 45, 46, 46], target = 47

Output: 2

Explanation:

1 + 46 = 47

2 + 45 = 47

Example 2:

Input: [1, 1], target = 2

Output: 1

Explanation:

1 + 1 = 2

Example 3:

Input: [1, 5, 1, 5], target = 6

Output: 1

Explanation:

[1, 5] and [5, 1] are considered the same, therefore there is only one unique pair that adds up to 6.

Two sum unique pairs Amazon Online Assessment
Two sum unique pairs Amazon Online Assessment

SOLUTION

Program: Two Sum Unique Pairs Solution in C++

#include<vector>
#include<iostream>
#include<unordered_set>
using namespace std;
int countUniquePairs_optimized(vector<int> nums, int target){
	unordered_set<int> seen;
	unordered_set<int> numsSet;
	int count = 0;
	for (int n : nums){
		int complement = target - n;
		if (numsSet.find(complement) != numsSet.end()){ // since we didnt add everything to the set yet, then we won't hit the case where the pair is itself. 
			// We found the complement
			if(seen.find(complement) == seen.end()){ // we have not seen this number yet
				count++;
			}
			seen.insert(n); // we have now seen/used this number for the overall count of unqiue pairs
			seen.insert(complement); 	// We can either add its complement or check for both the complement and n in seen in line 49. I think this way is faster.. slightly. We have to add its complement because
			// we might get to a case where we double count once we get to the complement number since it doesnt know we have seen n before and counted it. 
		}
		numsSet.insert(n);
	}
	return count;
}
int main (void){
	vector<int> test1 = {1, 1, 2, 45, 46, 46};
	int target1 = 47;
	vector<int> test2 = {1, 1};
	int target2 = 2;
	vector<int> test3 = {1, 5, 1, 5};
	int target3 = 6;
	int res = countUniquePairs_optimized(test3, target3);
	cout << "result is " << res << endl;
	return 0;
}

Program: Two Sum Unique Pairs Solution in Java

public static int getUniquePairsOpti(int[] nums, int target){
    Set<Integer> seen =  new HashSet<>();
    Map<Integer, Integer> map = new HashMap<>();
    int ans = 0;
    for (int num : nums){
        if (map.containsKey(num)){
            int key = map.get(num)*10 + num;
            if (! seen.contains(key)){
                ans++;
                seen.add(key);
            }
        } else {
            map.put(target-num, num);
        }
    }
    return ans;
}

Program: Two Sum Unique Pairs Solution in Python

def uniqueTwoSum(nums, target):
  ans, comp = set(), set()
  for n in nums:
    c = target-n
    if c in comp:
      res = (n, c) if n > c else (c, n)
      if res not in ans:
        ans.add(res)
    comp.add(n)
  return len(ans)

Related: Amazon Online Assessment 2022 Questions List