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
Goku007
What is the max size of the array and the max element in the array?
ajay
You can take the example that has been provided and try to solve.
Goku007
#include
using namespace std;
int main() {
int a[100];
for(int i=0;i>n>>k;
for(int i=0;i>x;
a[x]++;
}
if(k==0)
{
for(int i=0;i<=100;i++)
{
if(a[i]==2)
{
cout<<i<<","<<i<<endl;break;
}
}
}
else
{
for(int i=0;i<=k/2;i++)
{
if(a[i]!=0)
{
if(a[k+i]==1)
{
cout<<i<<","<<k+i<<endl;
break;
}
}
}
}
return 0;
}
// 7 24
// 4 2 5 8 21 34 10
Assumptions : The max element of the array is 100.
Hope this works!
Goku007
Above code got messed up:
Goku007
It is getting messed up idk why??
ajay
This is the default comment section, it automatically removes the leading spaces. In the coming weeks shall move to paid ones. There you shall have more control over the style.
Goku007
Can this problem be used by hashing?
ajay
shall let you know
Zanjo
Using hashmap:
https://pastebin.com/KEq0HcF4
Rohit Hegde
ajay
Hi Rohit Hegde,
I would like to know which language is it? as it will help other readers.