ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

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

prodevelopertutorial July 11, 2018

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:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io