Tuesday, November 1, 2011

Consecutive pairs with equal sum

Given two sorted arrays. Find pairs of consecutive numbers from both the arrays such that their sum is equal.

Ex. 
Array1 {1,5,7,8,9,10}
Array2 {2,3,3,5,6,11}

Output:
1,5 AND 3,3
8,9 AND 6,11

Solution :

set p = size of A[] and q = size of B[]
set i=0,j=0
while(i<p-1 and j<q-1){
    if((A[i]+A[i+1])==(B[j]+B[j+1])){
        print A[i],A[i+1],B[i] and B[i+1]
        i=i+1 and j=j+1
    }
    else if((A[i]+A[i+1])>(B[j]+B[j+1])){
        j++
    }
    else {
        i++;
    }
}

Complexity :
  • Time : O(N) 
  • Space : O(1)

No comments:

Post a Comment