IITD_2011 Interview

Question

#IITD_2011

If we are give a sorted array and we have to find two elements which sum to a number x.

Answer 1

let a[n]  be the array. Take p=0, q=n-1;

while(p<q)

{ 

If(a[p] +a[q] == x) output x and y;break;

else if (a[p] +a[q] >x)  q--;

else  p++;

} 

if(p==q) required elements not present in given array;

TimeComplexity :wc O(n)

 Extra Space Required :O(1)

Answer 2

If the array is sorted in the increasing order, we can scan the array from the two ends of the array to find the matched pair. Therefore, the time complexity is O(n) and the space complexity is O(1).

code:

def find_sum_sort(arr,x):
    low = 0
    high = len(arr) - 1
    found = 0
    while low < high:
        sum = arr[low]+arr[high]              //adding first and last element of the array
        if sum == x:                          
            ll = low + 1
            while arr[ll] == arr[low]: ll += 1 
            if arr[low]==arr[high]:            
                for i in range(low, ll):
                    for j in range(i+1, ll):
                        found += 1
                        print "%d: [%d]=%d - [%d]=%d"%(found, i, arr[i], j, arr[j])
                return found
            hh = high - 1
            while arr[hh] == arr[high]: hh -= 1
            for i in range(low, ll):
                for j in range(hh+1, high+1):
                    found += 1
                    print "%d: [%d]=%d - [%d]=%d"%(found, i, arr[i], j, arr[j])
            low = ll
            high = hh
        elif sum < x:
            low += 1
        else:
            high -= 1
    return found

Reference: http://www.cs.uml.edu/~jlu1/doc/codes/findSum.html