We will use binary search for this one. Suppose our first array (called A) is sorted in ascending order. For a number x, if x+A[i] is greater than 10000 we can say for sure that for all I>i, x+A[I] will > 10000 which means for every B[i] we need to take initial segment 1..n check for the middle element and see if the sum of the element from B and the middle element of A is greater than 10000 then we should check for the segment 1...mid else mid...n. Check the source code for a better understanding.
No comments:
Post a Comment