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.
See Also : Amazon Online Assessment Questions 2021 Preparation
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)Related:
- 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
Weekly Contest 247
- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony
Biweekly Contest 55
- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System
June Long Challenge 2021 Solutions
- Maximum Frequent Subarray Sum solution codechef
- Dual Distance solution codechef
- Optimal Xor Set solution codechef
- Minimum Subtree Cover solution codechef
- Minimum Dual Area solution codechef
- Bitwise Tuples solution codechef
- Shortest Route solution codechef
- Bella ciao solution codechef
- Summer Heat solution codechef