Question

Suppose you are given an integer c and an array, A, indexed from 1 to n, of n integers in the range from 0 to 5n (possibly with duplicates). i.e. 0 <= A[i ] <= 5n " I = {1, .., n}.

a.) Write an efficient algorithm that runs in O(n) time in a pseudo code for determining if there are two integers, A[i] and A[j], in A whose sum is c, i.e. c = A[i] + A[j], for 1 <= i < j <= n. Your algorithm should return a set of any pair of those indices (i , j). If there were no such integers, return (0, 0).

b.) Implement your algorithm of Q7 either in Python programming language where A[1:10] = [30, 25, 10, 50, 35, 45, 40, 5, 15, 20] and c = 40.

Answer 1

a)

Function containsIntegers(array: A[], int: ar_size, int: c)
1) Sort the array in non-decreasing order.
2) Initialize two index variables to find the candidate elements in the sorted array.
       (a) Initialize first to the leftmost index: l = 0
       (b) Initialize second  the rightmost index:  r = ar_size - 1
3) Loop while l < r.
       (a) If (A[l] + A[r] == sum)  then return (L, R)
       (b) Else if( A[l] + A[r] <  sum )  then l++
       (c) Else r--    
4) No candidates in whole array -> return (0, 0)

CODE

def containsIntegers(A, arr_size, c):

  quickSort(A, 0, arr_size-1)

  l = 0

  r = arr_size-1

  

  # traverse the array for the two elements

  while l<r:

    if (A[l] + A[r] == c):

      return (l, r)

    elif (A[l] + A[r] < c):

      l += 1

    else:

      r -= 1

  return (0, 0)

def quickSort(A, si, ei):

  if si < ei:

    pi = partition(A, si, ei)

    quickSort(A, si, pi-1)

    quickSort(A, pi + 1, ei)

def partition(A, si, ei):

  x = A[ei]

  i = (si-1)

  for j in range(si, ei):

    if A[j] <= x:

      i += 1      

      A[i], A[j] = A[j], A[i]

    A[i + 1], A[ei] = A[ei], A[i + 1]

  return i + 1

  

A = [30, 25, 10, 50, 35, 45, 40, 5, 15, 20]

c = 40

l, r = containsIntegers(A, len(A), c)

if (l != 0 or r != 0):

  print("%d, %d" %(l, r))

else:

  print("Array doesn't have two elements with the given sum")