Blog Logo
Research Scientist @ Foundation AI
·
read
Image Source: https://www.pixelstalk.net/mathematics-hd-desktop-wallpapers/
· · ·

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)
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)
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

· · ·