Google Interview Question
In a sorted array, find the number of pairs whose sum is less than a given value.
Interview Answers
You don't have to traverse the whole array. You only need to traverse till the indexes where the element are smaller than the given number.
The simplest way is to use two for loops:
The first loop should start from i=0 to i
Of course you don't have to traverse the entire array.
A distribution independent (with respect to the numbers in the array) solution is to first search for two numbers the value itself and half that value. These can be done together in log2(n). All pairs of numbers below half that value are good so combinatorics gives you directly how many of those you have. There are technicalities about distinct and sorted pairs that depends on what is actually required. All pairs of numbers above that value can be ignored. So your computation has to concentrate within these 2 bounds. One way is to do a scan and keep for each number how far down the difference between the value and this number is found. From that computing the numbers of pairs is trivial.
You can discuss what happens for these technically murky situations repeated numbers and order vs unordered pairs.
You can discuss what happens if the distribution of numbers doesn't change so you can precompute some of these values or get really accurate guesses for subsequent computations. You should be able to get essentially search complexity (log2(n)) for a query if the distribution of numbers is stable and you can cache some of these values.