Array ( [0] => [1] => questions [2] => Arrays [3] => Two-SUM ) Arrays | Two SUM | THE INQUISITIVE






Two SUM

LEVEL:Beginner

Description

Given the Array of integers and the S value. You have to return the pair whose sum is equal to the given S. If there are two occurrences return the first occurrence. If there is no occurrence return NULL.

Input Format

First line the number n. Takes n values in the next line Next line takes the values of S.

Output Format

Returns the pairs which have the sum of the given number without repetition.


Example 1:

Input
5
1 2 3 4 5
5
Output
1 4
Example 2:

Input
3
4 8 7
2
Output
Null
Example 3:

Input
7
1 1 1 1 1 1
2
Output
1 1

oops

Login to see Discussion




Approach

Approach 1: Brute Force

Step-i) Run 2 for loops for accessing the elements pair wise with 2 variables using I and j.
Step-ii) Inside the 2nd for loop check a condition.
Step-iii) If the sum of elements at i th position and j th position is equal to the fixed sum, then return elements at ith and j th index.

Time Complexity: O(N^2)
Space Complexity: O(N)

Approach 2: Sort the array

Step-i) Sort the given array.
Step-ii) initialize i with 0 and j with length – 1.
Step-iii) iterate a loop until iStep-iv) if sum i th element and j th element is equal to the fixed sum, return them.
Step-v) if sum is greater than fixed sum, decrement j by 1.
Step-vi) if sum is lesser than fixed sum, increase i by 1.

Time Complexity: O(Nlog(N))
Space Complexity: O(N)

Approach 3: Using a=sum-b concept

Step-i) Initialize a empty HashMap.
Step-ii) Iterate through the array and check whether element a is in the hash map.
Step-iii) If not in hash map, insert the element a and sum-a in hashmap.
Step-iv) If the value a is already present in the hash map, return a and sum-a.

Time Complexity: O(N)
Space Complexity: O(N)


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






     Recommended Questions      

Topic: Arrays

Beginner

1. Arithmetic Progression2. Geometric Progression3. Harmonic Progression4. No of triangles 5. Area of Polygon6. Trailing Zeros7. Min Platforms 8. Trapping Rain 9. Jump numbers10. Segregation of 0’s and 1’s11. Two SUM12. Triplet sum 13. Diagonal Sum14. Addition of two matrixes15. Subtraction of two matrixes16. Multiplication of two matrixes17. Transpose of given array18. Spiral Matrix19. Most Frequent Element20. Majority Element 21. Max difference 22. Odd occurring23. Second Largest and Second Smallest24. Next greater number25. Count Unique Elements26. Common elements 27. Removing Duplicates28. Balanced Array29. Rotating Array by k times30. Reverse Array31. Wave Array32. Merge arrays 33. Constraint Sort34. Find element in Sorted rotated array35. Sub Array Sum36. Largest subarray of 0’s and 1’s 37. K-Sub Array38. Max subarray sum39. Contiguous Square Sum