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)

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.

You may also like

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