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)
18
1import 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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫