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.
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 Questions:
- Robot Bounded in Box
- Number Game
- Find All Combination of Numbers Sum to Target / Shopping Options
- Fill the Truck
- Music Pairs
- Slowest key
- Five Star Seller
- Split String Into Unique Primes
- Storage Optimization
- Minimum Difficulty of a Job Schedule
- Autoscale Policy, Utilization Check
- Optimal Utilization
- Merge Two Sorted Lists
- Two Sum Unique Pairs
- Shopping Patterns
- Reorder Data in Log Files
- Top K Frequent Words
- Trees Height
- Counting Binary Substrings Amazon OA Solution
- Grid Connections Amazon OA Solution
- Shipment Imbalance Amazon OA Solution
- Max Profit Amazon OA Solution
- Find Lowest Price Amazon OA Solution
- Simple Cipher Amazon OA Solution
- Decode String Frequency Amazon OA Solution
- Valid Discount Coupons Amazon OA Solution
- Count Maximum Teams Amazon OA Solution
- Minimum Coin Flips Amazon OA Solution