Sponsored
Sponsored
This approach involves sorting the data first and then using a two-pointer technique. By sorting, we can simplify the problem as the elements will be in order. The two-pointer method then efficiently checks possible solutions by limiting the number of checks needed.
Time complexity is O(n log n) due to sorting, and space complexity is O(1).
1#include <stdio.h>
2#include <stdlib.h>
3
4int cmpfunc(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8void findPair(int arr[], int n, int sum) {
9 qsort(arr, n, sizeof(int), cmpfunc);
10 int left = 0, right = n - 1;
11
12 while (left < right) {
13 int current_sum = arr[left] + arr[right];
14
15 if (current_sum == sum) {
16 printf("Pair found: (%d, %d)\n", arr[left], arr[right]);
17 return;
18 }
19 if (current_sum < sum)
20 left++;
21 else
22 right--;
23 }
24 printf("No pair found\n");
25}In this solution, we begin by sorting the array using the qsort function from the standard library. Next, we use two pointers initialized at the beginning and end of the array. We iterate, moving the pointers based on their summed value compared to the target, hence optimizing the search.
This approach uses a hash table (or dictionary) to keep track of the elements and their complements needed to reach the target sum. By utilizing this lookup, we can reduce the problem to a linear time complexity.
Time complexity is O(n) assuming uniform distribution of hash function (no collisions), and space complexity is O(n).
1
The JavaScript implementation employs a Set to track values seen during iteration. This ensures direct and rapid determinations of complement existence, producing real-time results optimally.