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.
