Menu
Given two sorted arrays of integers, a and b, and an integer c, I have to find i,j such that:
a[i] + b[j] <= c
and a[i] + b[j] is large as possible.
The best solution I can think of is in O(nlogn) time, taking every integer from first array and finding the lower bound of "c-a[i]".
Can anyone suggest me a better way to do this (maybe in O(n) time)?
537
Traverse the array and for each i, do the following : Find the lower bound for x/arr[i] in the sub-array on the right of arr[i], i.e., in subarray arr[i+1..n-1]. Let it be denoted by l. Find the upper bound for x/arr[i] in the sub array on the right of arr[i], i.e., in sub array arr[i+1..n-1].
Follow the steps below to solve the given problem: Initialize the count variable with 0 which stores the result. Iterate arr and if the sum of ith and jth [i + 1…..n – 1] element is equal to sum i.e. arr[i] + arr[j] == sum, then increment the count variable. Return the count.
Thinking a bit about it, then you could ask yourself:
"Is it necessary, each time, to search in the sorted b-array for successive values from a[]?"
83
I think you dont have to search the whole array b[] next time.......u have to search in between starting of array b and the lowest bound u found till now....for the next element in a[].It would definitely reduce your time complexity...and when u find the given target 'c' you must stop your search.
45
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
