Amazon Online Assessment (OA) - Two Sum - Unique Pairs
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.
Try it yourself
Solution
Prereq: Two sum
Explanation
Implement a regular solution for the two-sum problem, but use a set to check for and discard duplicates.
Implementation
1from typing import List
2
3def two_sum_unique_pairs(nums: List[int], target: int) -> int:
4 seen = set()
5 complement = set()
6 for num in nums:
7 if target - num in complement:
8 pair = (num, target - num) if num < target - num else (target - num, num)
9 seen.add(pair)
10 complement.add(num)
11 return len(seen)
12
13if __name__ == "__main__":
14 nums = [int(x) for x in input().split()]
15 target = int(input())
16 res = two_sum_unique_pairs(nums, target)
17 print(res)
181import java.util.Arrays;
2import java.util.HashSet;
3import java.util.List;
4import java.util.Scanner;
5import java.util.Set;
6import java.util.stream.Collectors;
7
8class Solution {
9 public static int twoSumUniquePairs(List<Integer> nums, int target) {
10 Set<Integer> seen = new HashSet<>();
11 Set<Integer> complement = new HashSet<>();
12 int ans = 0;
13 for (Integer num : nums) {
14 if (complement.contains(target - num) && !seen.contains(num)) {
15 // (num, target - num) is a pair that sums to the target
16 ans++;
17 // mark num and target - num as seen so that when we see (target - num, num) it won't be counted again
18 seen.add(num);
19 seen.add(target - num);
20 }
21 complement.add(num);
22 }
23 return ans;
24 }
25
26 public static List<String> splitWords(String s) {
27 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
28 }
29
30 public static void main(String[] args) {
31 Scanner scanner = new Scanner(System.in);
32 List<Integer> nums = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
33 int target = Integer.parseInt(scanner.nextLine());
34 scanner.close();
35 int res = twoSumUniquePairs(nums, target);
36 System.out.println(res);
37 }
38}
39