Two sum unique pairs Amazon Online Assessment

Two Sum Unique Pairs Solution Amazon OA 2021

by

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.

Also See: Amazon OA Online Assessment 2021 Questions and Answers

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.

Solution

Program 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 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 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)

Also See: AMCAT Study Materials, Preparation Guide

Also See: Microsoft Online Assessment Questions and Solution

Amazon Online Assessment Test Questions:

Leave a Comment