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).
using System.Collections.Generic;
public class PairFinder {
public static void FindPair(int[] arr, int sum) {
HashSet<int> complements = new HashSet<int>();
foreach (var number in arr) {
int complement = sum - number;
if (complements.Contains(complement)) {
Console.WriteLine($"Pair found: ({number}, {complement})");
return;
}
complements.Add(number);
}
Console.WriteLine("No pair found");
}
}C# offers a HashSet class to properly insert elements and check for complements in linear time. This aids in swift detection of pairs without needing to scan through remaining elements unnecessarily.