# 5 Best Ways to Find Any Two Numbers Summing to K in Python Lists

Rate this post

π‘ Problem Formulation: You have been given a list of integers, and you’re required to find any two distinct numbers in that list which add up to a specified number `k`. For instance, if the input list is `[1, 2, 3, 4]` and `k` is 5, the output should be a tuple like `(1, 4)` or `(2, 3)`.

## Method 1: Brute Force

The brute force approach checks every possible pair of numbers in the list to see if they add up to `k`. This is done using nested loops. Although this method is straightforward and easy to implement, it is not optimal for large lists due to its `O(n^2)` time complexity.

Here’s an example:

```def find_pair_brute_force(nums, k):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == k:
return nums[i], nums[j]
return None

pair = find_pair_brute_force([3, 4, 5, 6], 9)
print(pair)```

Output: `(3, 6)`

This code snippet defines a function `find_pair_brute_force` which takes a list of numbers and the target sum `k`. It iterates over each element, using nested loops to check every pair’s sum. When a pair summing to `k` is found, it returns the pair, otherwise it returns `None`.

## Method 2: Sorting and Two-Pointer Technique

This method involves sorting the list first, and then using a two-pointer technique where one pointer starts at the beginning and the other at the end of the sorted list. This method is more efficient with a time complexity of `O(n log n)` due to sorting.

Here’s an example:

```def find_pair_two_pointer(nums, k):
nums.sort()
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == k:
return nums[left], nums[right]
elif current_sum < k:
left += 1
else:
right -= 1
return None

pair = find_pair_two_pointer([3, 4, 5, 6], 9)
print(pair)```

Output: `(3, 6)`

The `find_pair_two_pointer` function sorts the list and initializes two pointers. It checks pairs and moves the pointers closer together until it finds a pair that adds up to `k`, at which point it returns the pair.

## Method 3: Using a Hash Table

By using a hash table (dictionary in Python), we can store numbers we’ve visited and check if the complement (k – current number) exists in O(1) average time complexity. This results in an overall time complexity of O(n).

Here’s an example:

```def find_pair_hash_table(nums, k):
complements = {}
for num in nums:
if k - num in complements:
return k - num, num
complements[num] = True
return None

pair = find_pair_hash_table([3, 4, 5, 6], 9)
print(pair)```

Output: `(3, 6)`

In this snippet, the `find_pair_hash_table` function creates a dictionary to store elements as keys. During iteration, it checks if the complement of the current element to achieve `k` is already in the dictionary, and returns the pair if found.

## Method 4: Binary Search for Complements

After sorting the list, we can use binary search to find the complement for each number, thus avoiding the two-pointer technique. This method has a time complexity of `O(n log n)` due to sorting and binary searching.

Here’s an example:

```import bisect

def find_pair_binary_search(nums, k):
nums.sort()
for i in range(len(nums)):
complement = k - nums[i]
j = bisect.bisect_left(nums, complement, i+1)
if j < len(nums) and nums[j] == complement:
return nums[i], nums[j]
return None

pair = find_pair_binary_search([3, 4, 5, 6], 9)
print(pair)```

Output: `(3, 6)`

The `find_pair_binary_search` function sorts the list and then uses the Python `bisect` module for efficient binary searching. For each element in the list, it searches for its complement that would add up to the target sum `k`.

## Bonus One-Liner Method 5: List Comprehension with a Set

As a quick solution, using list comprehensions combined with a set can find a pair that adds to `k`, although it lacks the efficiency of method three and four on larger lists due to creation of intermediary tuples.

Here’s an example:

```def find_pair_set_comprehension(nums, k):
nums_set = set(nums)
pair = next(((num, k - num) for num in nums if (k - num) in nums_set), None)
return pair

pair = find_pair_set_comprehension([3, 4, 5, 6], 9)
print(pair)```

Output: `(3, 6)`

This one-liner `find_pair_set_comprehension` function converts the list to a set for faster lookups. Then, it uses list comprehension to iterate once through the numbers, checking for the presence of the complement in the set.

## Summary/Discussion

• Method 1: Brute Force. Simple to implement. Not recommended for large lists due to inefficiency.
• Method 2: Sorting and Two-Pointer Technique. More efficient than brute force. Requires the list to be mutable for sorting.
• Method 3: Using a Hash Table. Highly efficient with linear time complexity. Slightly more memory usage due to hash table.
• Method 4: Binary Search for Complements. Efficient when dealing with sorted lists. Requires sorting step.
• Method 5: List Comprehension with a Set. Elegant one-liner. Not as efficient as other methods on larger datasets due to the creation of intermediary tuples.