Question

Given an unsorted integer array A of size n, develop an 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

Given : unsorted array A[] of size n

Aim : Find two indexes i and j such that A[i] + A[j] = 100

Approach : This can be done using the concept of Hashing, because we want to reduce the time taken for lookup in an array.For Hashing this lookup time is O(1),that is constant time.(The notation used is BigO notation). Hashing is the concept of using a key to store a value using a dictionary. If you are using C++, this dictionary will be in the form of an unordered map. Here the value of a particular dictionary element will be the index value-i in the original array and the key used to store this value will be the A[i].

PseudoCode :

1) Take the input from the user and store the array in a variable named A,if not done so already.Also store the size of array in the variable N which is the size of the array.

2) Create an empty dictionary (unordered map for C++) named myDict.

3) Run a loop for i = 1 to N-1. For every iteration perform the following operation

if A[i] == 50 return {i,i}

else myDict[A[i]] = i (update the dictionary)

increment i by 1

4) Run a loop for i = 1 to N-1. For every iteration perform the following operation

if myDict[100 - A[i]] is not NULL then return {myDict[100 - A[i]] , myDict[A[i]] }

increment i by 1

5) If the function has not returned anything by now the return " No such pairs of i and j exist "

Analysis :

The time complexity of this solution is O(n). It cannot be improved beyond this.The first loop has runs N iteration,hence takes O(n) time.The second loop will also take O(n) time ,considering the worst case. Thus O(n) + O(n) = O(n).

NOTE

If the array has repetitve values, for example the value 56 appears at both index 4 and 10 ,myDict will store the largest value of array index which in this case is 10.This will be used for lookup in this algorithm