Given an array of integers in ascending order, return index of the two numbers such that they add up to a specific key provided.

Solution Description:

This problem can be solved in 2 different ways.

Solution 1: Brute Force Technique

Explanation: In this technique, we shall be taking 2 loops. Outer Loop and Inner Loop.

Step 1: First take the first element of the outer loop and add it to every other element from the inner loop array. And check if the sum is equal to the “key”. If it matches we return from the loop.

Step 2: Else we go for the second element and add it to every other element of the inner loop.

We continue the above steps until we reach the end of the outer loop. If we get a match program will return 1 else, it will return 0.

Example:

Take the array [1,2,3,4] and “key” is 7.

Pass 1:
      1 + 2 = 3 false
      1 + 3 = 4 false
      1 + 4 = 5 false

Pass 2:

    2 + 3 = 5 false.
    2 + 4 = 6 false.

Pass 3:
    3 + 4 = 7 true.

Time Complexity:

Since the program is using 2 for loops, the time complexity will be O(n^2).

Solution in C language:

# include <stdio.h>

int checkSum(int arr[], int arr_size, int key)
{
	int i = 0;
	int j = 0;
	int sum = 0;

	for (int i = 0; i < arr_size; ++i)
	{
		for (int j = i+1 ; j < arr_size; ++j)
		{
			sum = arr[i] + arr[j];
			if (sum == key)
			{
				return 1;
			}

		}

	}
	return 0;
}



int main()
{
    int array[] = {1,2,3,4,5,6};
    int key = 11;
    int array_size = 6;
    
    if(checkSum(array, array_size, key))
        printf("Array has two elements with given key\n");
    else
        printf("Array doesn't have two elements with given sumkey\n");
     return 0;
}

Output:

Array has two elements with given key

Solution 2: Hashing Technique

In this technique is useful when the range of the number is known. For our program we have taken it as 1000.

Explanation:

Take an empty hash table say hashTable[].

Then we check if hashTable[ key – array[i] ] is set, then we shall print the pairs,

Else we update the vavlue 1 to s[ array[i] ].

Hence the for loop will be:

for(i = 0; i < array_size; i++)
{
	temp = key - array [i];
	if (temp >= 0 && hashTable[temp] == 1)
		printf("Elements are present");
	s[ array[i] ] = 1;
}

Example:

Let us take the input [1, 2, 3, 4, 5] key is 9.

Pass 1:
i = 0;
	temp = 9 - 1 = 8
		if( 8 >= 0 && hashTable[8] == 1)
			false
	hashTable[ 1 ] = 1;


Pass 2:
i = 1;
	temp = 9 - 2 = 7
		if( 7 >= 0 && hashTable[7] == 1)
			false
	hashTable[ 2 ] = 1;


Pass 3:
i = 2;
	temp = 9 - 3 = 6
		if( 6 >= 0 && hashTable[6] == 1)
			false
	hashTable[ 3 ] = 1;


Pass 4:
i = 3;
	temp = 9 - 4 = 5
		if( 5 >= 0 && hashTable[5] == 1)
			false
	hashTable[ 4 ] = 1;


Pass 5:
i = 4;
	temp = 9 - 5 = 4
		if( 4 >= 0 && hashTable[4] == 1)
			true
	hashTable[ 5 ] = 1;

C program to implement the same:

# include <stdio.h>
#define MAX 100000
 
void checkPairs(int array[], int array_size, int key)
{
  int i, temp;
  int hashTable[MAX] = {0}; 
	for(i = 0; i < array_size; i++)
	{
		temp = key - array [i];
		if (temp >= 0 && hashTable[temp] == 1)
			printf("Elements are present\n");

		hashTable[ array[i] ] = 1;
	}
}



int main()
{
    int array[] = {1,2,3,4,5,6};
    int key = 11;
    int array_size = 6;
    
	checkPairs(array, array_size, key);
       
     return 0;
}

List Of Tutorials available in this website: