Example:
Input:
{4, 2, 5, 8, 21, 34, 10} key = 24
Output:
Pair found (34, 10)
This problem can be solved in 2 ways.
Solution 1: Brute force method.
Explanation:
Step 1: Take 2 loops, outer loop and an inner loop.
Step 2: The element from outer loop will pick every other element in the inner loop and checks if the difference matches or not.
Time complexity will be O( n ^2 ).
Example:
Input {4, 2, 34, 10} key = 24
Pass 1: 4 – 2 or 4 – 2 == 24? No 4 – 34 or 34 – 4 == 24? No 4 – 10 or 10 -4 == 24? No
Pass 2: 2 - 4 or 4 – 2 == 24? No 2 – 34 or 34 – 2 == 24? No 2 – 10 or 10 – 2 == 24? No
Pass 3: 34 – 10 or 10 - 34 == 24 ? Yes. Return the elements.
Solution 1 in c:
#include<stdio.h> void findElementsWithKeyDifference(int arr[], int length, int key) { int outer_loop = 0; int inner_loop = 0; int diff = 0; for(outer_loop = 0; outer_loop < length; outer_loop ++) { for(inner_loop = outer_loop+1; inner_loop < length; inner_loop++) { if( (arr[inner_loop] - arr[outer_loop] )== key || (arr[outer_loop] - arr[inner_loop]) == key) { printf("Elements found %d and %d\n", arr[outer_loop], arr[inner_loop] ); return ; } } } printf("Elements not found" ); } int main() { int arr [100] = {4, 2, 5, 8, 21, 34, 10}; int key = 24; int length = 7; findElementsWithKeyDifference(arr, length, key); }
Output:
Elements found 34 and 10
Solution 2: Sort the array and then find the elements are present or not.
Step 1: Sort the array in ascending order.
Step 2: Take 2 variables “i” and “j” initialize “ i = 0” and “j = 1”
Step 3:
Inside while loop, Check if a[j] – a[i] == key If true return Else If a[j] – a[i] < key Increment j Else Increment i Loop until “i” and “j” value is less than array length.
Here the time complexity for the second step will be O ( n );
Solution 2 in c:
#include<stdio.h> void swap (int *num_1, int *num_2) { int temp = *num_1; *num_1 = *num_2; *num_2 = temp; } void bubble_sort (int array[], int length) { int outer_loop = 0; int inner_loop = 0; for(outer_loop = 0; outer_loop < length - 1; outer_loop ++) { for(inner_loop = 0; inner_loop < length - outer_loop - 1 ; inner_loop ++) { if(array [inner_loop] > array[inner_loop+1]) { swap(&array[inner_loop], &array [inner_loop+1]); } } } } void findElementsWithKeyDifference(int arr[], int length, int key) { int i = 0; int j = 1; while(i < length && j < length) { if(i != j && arr [j] - arr[i] == key) { printf("Elements found %d and %d\n", arr[i], arr[j] ); return ; } else if (arr [j] - arr[i] < key) j++; else i++; } printf("Elements not found" ); } int main() { int arr [100] = {4, 2, 5, 8, 21, 34, 10}; int key = 24; int length = 7; bubble_sort (arr, length); findElementsWithKeyDifference(arr, length, key); }
Output:
Elements found 34 and 10