Given an unsorted array, and a key. Find 2 elements such that the difference between the elements is equal to the key.

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

List Of Tutorials available in this website: