Author : Pratik Gholap
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials
It is recommended to go through previous hashing tutorials to get a better understanding.
PART _ (Given an array and target 'x', Find out the pair from array whose sum forms the number 'x' when both the numbers of the pair are added) :
Given an array arr1 and number 'x', To find if a pair exists in arr1 which can be added to make number 'x'.
Example-1:
Input:
arr1 = {0, -1, 2, -3, 1}
x = -2
Output: true
(-3, 1) or (1,-3) are the pairs which exist in arr1 which makes sum equal to x (-3+1=-2 and 1-3=-2)
Explanation: Calculate the sum of all possible pairs and return (true/false) if the value of any pair is equal/not equal to 'x'.
Example-2:
Input:
arr1 = {1, -2, 1, 0, 5}
x = 0
Output: false
Explanation: No sum of pairs in array has sum as 0 , therefore , false will be the answer
Approach 1: Brute-Force Approach
In the problem , we have to find the pair so to find the pair in the array, we can take one element from the array and check the remaining part by adding every element with the taken element if we get the sum equal to the number 'x' we will return true otherwise false.
So this can be done by using 2 'for' loops, First Loop we will use to take first element and Second loop will be used to traverse the array to find the second number.
Algorithm:
- Take the input for array 'arr' and number 'x'.
- Entering inside the loop by maintaining each element at a time as first element. starting from i = 0 till i < size-1 (size -1 used since we have to find the pair therefore we are traversing till second last indexed element so that we can check it if it makes pair with the last element, and also last element doesn't have any element further to make a pair with it).
- Entering inside the 2nd for loop starting from j = i+1 till j < size .
- Check if sum of arr[i] + arr[j] = x, if it is true then jump to point 8.
- If point 4 is false then repeat point 3.
- If we don't get sum by traversing the array then repeat the point 2.
- If we don't get the sum which is equal to 'x' then return 0 and jump to point 8.
- End the program.
Time Complexity : O(n^2)
Space Complexity : O(1)
Piece of code(C++) :-
Approach 2: Hashing
As we see the above Brute-Force approach, it will work good for small size of array but for large size it will be inefficient in terms of computing the problem so we need to optimise the solution to the problem. We can do this using hashing, In this problem we will use set which will help us in maintaining the elements presence and help in accessing them faster.
So basically, we will use a single 'for' loop in which for iteration we will take the difference of 'x' and 'arr[i]' and check if that difference value is present in the set . We are using set(unordered_set) as HashTable in this problem.
Algorithm:
- Take input for array 'arr' and number 'x'.
- Declare the set as pairSet.
- Enter inside the for loop from i = 0 till i < size
- Take the difference of 'x' and 'arr[i]' and store it in 'temp'.
- check if 'temp' value is present in pairSet till end, if it's present then return 0 (means true)then jump to point 8.
- If point 5 is false then repeat insert the value of 'arr[i]' in the pairSet and repeat the point 3.
- If we reach till this point return -1(indicating false).
- End the program.
Time Complexity : O(n)
Space Complexity : O(n)
Piece of code(C++) :-
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials