Is there a way to mathematically generate a given index of a sorted permutation sum array given the source set in O(1) or O(log N) time?

user_2533504 0
Viewed 92

I'm given a set of integers of size N in sorted, ascending order. For simplicity, this array "arr" is as follows: [a0, a1, a2, ..., aN]. I need the array of the sum of all pairs ai and aj, with duplicates allowed: [a0 + a0, a0 + a1, a0 + a2, ..., a1 + a0, a1 + a1, ... aN + aN], size N^2. However, I need it in sorted order to binary search across it (in O(log(N^2)) time) without having to generate the entire array, which would take O(N^2 log(N^2)) time. As a binary search only needs the values of the array at certain indices, I was wondering if there was a mathematical function to determine the value of the sorted permutation sum array given a specific index (e.g. value(3) would return ak + am), allowing me to binary search across the array without generating it in full? I was thinking something like:

int value(int index) {
     return arr[index/N] + arr[index%N];
}

but this doesn't take into account that the value of arr[i] + arr[k] may be greater than arr[i+1] + arr[k-5], for instance, even though arr[i+1] > arr[i]. TLDR; is there any way I could partition in less than O(N) time for this special case of array? For my own purposes, I could also accept a solution that generates the entire sorted array in less than O(N^2) time.

partitioning time-complexity sorting arrays algorithm
1 Answers

You will not be able to generate the entire 2D array in time less than O(N^2), because you need to do O(1) work to append/insert each value into your array, and there's N^2 elements to do this for. This automatically entails O(N^2) work.

However, you may be able to query without constructing the full array. I highly suspect that you won't be able to beat O(n) time. The reason I say that is because the only reason we can query a sorted list in O(log n) time is because we've put in prior work to sort those elements, which required inspecting each element and doing some work (thus, at least O(n)), and my gut tells me we're in a similar scenario here, only we haven't yet done the necessary precomputation.

Now, you can query it in O(n) time as is. Start by initializing two pointers- base and count, where base points to the first element in the list, and count points to the last element. Also initialize an integer total to 0. For each step, do the following:

  • move count backwards (towards the first element) until the value count points to plus the value base points to sum to less than the query value (*count + *base < query).
  • add the count (the index / offset) to total
  • move base forwards
  • repeat until just after either pointer hits its far end (inclusive)

The base pointer represents a value that we wish to know how many other elements could be added to and still be less than the query value. The pointer count indicates the last element that can can be added to base and still be less than the query value, so adding count (the index) for each base gives us the total number of pairs of elements that would sum less than the query. All together, this is O(n) since we just iterate over the initial array, once in each direction, at most.

user_62210240
Related