· · ·
Q: Given an array find a pair of element with the given sum.
Input:
a = [8, 7, 2, 5, 3, 1]
s = 10
Output:
(8, 2)
(7, 3)
Algorithms:
- Hashing:
- Complexity:
- Time: O(n)
- Space: O(n)
- Complexity:
a = [8, 7, 2, 5, 3, 1]
s = 10
h = {}
for idx, elem in enumerate(a):
h[elem] = idx
diff = h.get(s-elem, None)
if diff != None and diff != idx:
print((elem, s-elem))
- Sorting:
- Complexity:
- Time: O(nlogn)
- Space: O(1)
- Complexity:
a = [8, 7, 2, 5, 3, 1]
s = 10
a.sort()
l = 0
h = len(a) - 1
while (l<h):
temp = a[l] + a[h]
if temp == s:
print((a[l], a[h]))
l = l+1
h = h-1
elif temp > s:
h = h-1
else:
l = l+1
REFERENCES:
500 Data Structures and Algorithms practice problems and their solutions
Find pair with given sum in the array
· · ·