Home Arrays Find two elements in an array such that their sum equals ‘K’. (Method 2)

Find two elements in an array such that their sum equals ‘K’. (Method 2)

by nikoo28
0 comment

Question: Given an array of n elements. Find two elements such that their sum is equal to a given element ‘K’ ?

Input: arr [] = {42, 23, 15, 16, 8, 4} and element K = 58
Output: 16, 42

We discussed the approach to this problem using 2 loops in this post. But obviously this was not a good approach as it had a time complexity of O(n2). The time taken to solve such a problem if the array has elements in range of million will be very high. We need to optimize this approach.

The steps involved in this algorithm will be:-

  • Sort the array. This operation takes a time of O(nlog(n))
  • Now maintain a variable lowIndex = 0 and highIndex = size-1.
  • Compute sum = arr[lowIndex] + arr[highIndex].
  • If (sum == K), then simply return the two variable.
  • If (sum < K), that means we need to add a bigger element to the sum, which can be obtained if we increment lowIndex, so
    if(sum<K)
        lowIndex++;
    
  • If (sum>K), that means we need to add a smaller number, the smaller number can be found if we decrement highIndex, so
    if(sum>;K)
        highIndex--;
    
  • We can repeat this process until we find the two digits. Else we return that no elements are found.

Here is an implementation of the above algorithm.

void twoElementsSumK(int arr[], int size, int K)
{
	//first sort the array
	quickSort(arr,size);

	//maintain the low and high index
	int lowIndex = 0;
	int highIndex = size-1;

	while(lowIndex < highIndex)
	{
		//get the sum
		int temp = arr[lowIndex] + arr[highIndex];

		//return if we find a match
		if(temp == K)
		{
			printf("The elements are :- %d %d",arr[lowIndex],arr[highIndex]);
			return;
		}

		//to change the low and high index
		if(temp < K)
			lowIndex++;
		else
			highIndex--;
	}
}

Time Complexity:- O(nlog(n))
Space Complexity:- O(1)

You can download the working example of code from here. Use your favorite text editor to open it (Notepad++, vim, gedit)

 

Method 3 – Use a hash table

We can also solve this problem using a hash table. Since out objective is to find two indexes of the array whose sum is K. Let us say those indexes are X and Y. That means arr[X] + arr[Y] = K.

What we need is, for each element of the input array arr[X], check whether K – arr[X] also exists in the input array. Now, let us simplify that searching with a hash table.

Algorithm:

  • For each element of the input array, insert into the hash table. Let us say the current element is arr[X].
  • Before proceeding to the next element we check whether K – arr[X] also exists in the hash table or not.
  • Existence of such number indicates that we are able to find the indexes.
  • Otherwise, proceed to the next input element.

Time Complexity:- O(n), considering the fact that searching in hash table takes time O(1).
Space Complexity:- O(n), to create and maintain the hash table.

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More