Question

Given an unsorted integer array A of size n, develop a python version pseudocode with time complexity as low as possible to find two indexes i and j such that A[i] + A[j] = 100. Indexes i and j may or may not be the same value.

Answer 1

#Using hashing technique we can solve this problem efficiently

# Algorithm

# 1. Initialize an empty hash set s.
# 2. Do following for each element A[i] in A[]
# 1. If s[100 – A[i]] is set then print the pair (A[i], 100 – A[i])
# 2. Insert A[i] into s.

# Pseudocode

# s = set()
# for(i in range(len(A)))
# find(100-A[i])
# if(find(100-A[i]) in s):
# print(i,j as A.index(find(100-A[i]),i))
# s.add(A[i])

# Python implimentation
def printPairs(A,size):
# Create an empty hash set
s = set()
for i in range(0,size):
temp = 100-A[i]
if (temp in s):
print("two indexes i,j such that are: {} and {}".format(A.index(temp),i))
s.add(A[i])

# Test the implimented function
A = [1, 55, 45, 40, 10, 8]
printPairs(A,6)

# Time Complexity Analysis

# As we can see here array is travelled only once so the time complexity will be O(n)
# We need extra space of n elements which is hash set so the space complexity is also O(n)