[c] Algorithm Problem

​

Given two sorted arrays of integers of size n,
i.e. a[n] and b[n], please find all pairs <value_1, value_2>

so that value from a[n], value_2 from b[n]
and value_1+ value_2=Constant, e.g. Constant=100.
and n<100.

Constraint: O(n) time, O(1) extra space

i cant think of any way of not using nested loop
pls help me

 

too loops and it's done

 

This is possible with O(n) time complexity but with O(n) space complexity as well.

 

The key part is that the arrays come pre sorted. If they were unsorted then it would be O(n^2) - which is using two simple nested loops checking every possible combination. Since they are sorted though, you can stop checking once your reach a number that is smaller. So your first loop is going through the a[] forwards, while the second loop is going to be going through b[] backwards. That way as the first loop gets closer to the end of a[], the second loop will get shorter and shorter because you will stop looping b[] when !(a > b[j]). So as you are increased the number of elements in both arrays your algorithm is increasing linearly. Hope this helps!