Finding Two Numbers in an Array that Sum to a Given Value?

Given an array `Arr` of `N` positive integers and a target sum `X`, the task is to determine if there exist two distinct elements in `Arr` whose sum is exactly `X`. This problem can be approached using various techniques, each with its own time and space complexities. Below, we explore five different approaches along with their explanations, time complexities, and space complexities. Additionally, Python and Java implementations are provided for each approach.

1. Two Sum using Naive Approach

Explanation

The naive approach involves using two nested loops to check all possible pairs in the array. For each pair, we check if their sum equals `X`.

Time Complexity

- Time Complexity: O(N^2)

- Space Complexity: O(1)

Python Code

 def two_sum_naive(arr, X):

    N = len(arr)

    for i in range(N):

        for j in range(i + 1, N):

            if arr[i] + arr[j] == X:

                return True

    return False

Java Code

    public class TwoSumNaive {

        public static boolean twoSumNaive(int[] arr, int X) {

            int N = arr.length;

            for (int i = 0; i < N; i++) {

                for (int j = i + 1; j < N; j++) {

                    if (arr[i] + arr[j] == X) {

                        return true;

                    }

                }

            }

            return false;

        }

    }

2. Two Sum using Sorting and Two-Pointers Technique

Explanation

First, sort the array. Then, use two pointers: one starting from the beginning (left) and the other from the end (right). If the sum of the elements at these pointers is greater than `X`, move the right pointer leftwards to decrease the sum. If the sum is less, move the left pointer rightwards to increase the sum.

Time Complexity

- Time Complexity: O(N log N) due to sorting + O(N) for the two-pointer traversal.

- Space Complexity: O(1)

Python Code

    def two_sum_two_pointers(arr, X):

        arr.sort()

        left, right = 0, len(arr) - 1

        while left < right:

            current_sum = arr[left] + arr[right]

            if current_sum == X:

                return True

            elif current_sum < X:

                left += 1

            else:

                right -= 1

        return False

Java Code

    import java.util.Arrays;

    public class TwoSumTwoPointers {

        public static boolean twoSumTwoPointers(int[] arr, int X) {

            Arrays.sort(arr);

            int left = 0, right = arr.length - 1;

            while (left < right) {

                int currentSum = arr[left] + arr[right];

                if (currentSum == X) {

                    return true;

                } else if (currentSum < X) {

                    left++;

                } else {

                    right--;

                }

            }

            return false;

        }

    }

3. Two Sum using Binary Search

Explanation

Sort the array. For each element in the array, perform a binary search for `X - arr[i]` in the remaining part of the array.

Time Complexity

- Time Complexity: O(N log N) due to sorting + O(N log N) for binary searches.

- Space Complexity: O(1)

Python Code

    import bisect

    def two_sum_binary_search(arr, X):

        arr.sort()

        for i in range(len(arr)):

            target = X - arr[i]

            j = bisect.bisect_left(arr, target, i + 1)

            if j < len(arr) and arr[j] == target:

                return True

        return False

Java Code

    import java.util.Arrays;

    public class TwoSumBinarySearch {

        public static boolean twoSumBinarySearch(int[] arr, int X) {

            Arrays.sort(arr);

            for (int i = 0; i < arr.length; i++) {

                int target = X - arr[i];

                int j = Arrays.binarySearch(arr, i + 1, arr.length, target);

                if (j > i) {

                    return true;

                }

            }

            return false;

        }

    }

4. Two Sum using Hashing

Explanation

Use a hash set to store elements of the array. For each element, check if `X - arr[i]` is already in the set. If found, the pair exists.

Time Complexity

- Time Complexity: O(N)

- Space Complexity: O(N)

Python Code

    def two_sum_hashing(arr, X):

        seen = set()

        for num in arr:

            if X - num in seen:

                return True

            seen.add(num)

        return False

Java Code

    import java.util.HashSet;

    public class TwoSumHashing {

        public static boolean twoSumHashing(int[] arr, int X) {

            HashSet<Integer> seen = new HashSet<>();

            for (int num : arr) {

                if (seen.contains(X - num)) {

                    return true;

                }

                seen.add(num);

            }

            return false;

        }

    }

5. Two Sum using Remainders

Explanation

Count elements based on their remainders when divided by `X`. Check for pairs of remainders that sum to `X`.

Time Complexity

- Time Complexity: O(N)

- Space Complexity: O(X)

Python Code

    def two_sum_remainders(arr, X):

        remainder_counts = [0]  X

        for num in arr:

            remainder_counts[num % X] += 1

        if remainder_counts[0] > 1:

            return True

        for i in range(1, X // 2 + 1):

            if i != X - i:

                if remainder_counts[i] > 0 and remainder_counts[X - i] > 0:

                    return True

            else:

                if remainder_counts[i] > 1:

                    return True

        return False

Java Code

    public class TwoSumRemainders {

        public static boolean twoSumRemainders(int[] arr, int X) {

            int[] remainderCounts = new int[X];

            for (int num : arr) {

                remainderCounts[num % X]++;

            }

            if (remainderCounts[0] > 1) {

                return true;

            }

            for (int i = 1; i <= X / 2; i++) {

                if (i != X - i) {

                    if (remainderCounts[i] > 0 && remainderCounts[X - i] > 0) {

                        return true;

                    }

                } else {

                    if (remainderCounts[i] > 1) {

                        return true;

                    }

                }

            }

            return false;

        }

    }

These five approaches provide different ways to solve the problem of finding two numbers in an array that sum to a given value `X`. Each method has its advantages and trade-offs in terms of time and space complexity. Depending on the size of the array and the constraints, one approach may be more suitable than the others.