is there a way to compare an Array A with another array B where B is xA + y under O(n^2)?

user_9677842 0
Viewed 74

given an array A of size n and another array called B. B is made of array A and 2 constants x and y where Bi = x * Ai + c (i => 0,1,2, … N-1) For example, if A : {3, 1, 5, 7} and x = 1 and y =2, then B : {5, 3, 7 ,9}

question: find out how many times A (j+1), (j+2), …. (n -1) > Bj for j E {0, 1, … n-1 }

Using the sample input above A: {3,1,5,7} B: {5,3,7,9}

the answer would be 3 since when j = 0, A3 > B0 (7>5) when j = 1, A2 > B1 (5>3) and A3 > B1 (7>3)

since there are only 3 possibilities of A j+1 …. n -1 > Bj for j E {0, 1, … n-1 }, the output will be 3

is there a way to solve this with an algorithm below O(n^2)? thanks!

algorithm
1 Answers

Why not insert elements of B into an order statistic tree as we iterate on A, and look up for each element we see in A, how many in the tree are lower? At each A_i, make sure all but only elements up to B_(i-1) are in the tree before the lookup. This wouldn't distinguish which Bs have higher A elements, but it seems like the question is only asking for the total number. O(n log n) time, O(n) extra space.

user_20347870
Related