Hello all,
Could someone share their thoughts on the problem mentioned below:
Given an array of sorted integers, find the number of unique triplets such that (a[i]*a[k])+a[j]=target and i<j<k.
Ex: A={1,3,3,5,5} and target=18 o/p should be {[3,3,5]} . Explanation a[1]*a[3]+a[2].
I know we can solve it in O(n^2) time.
Ques-1: Can we solve it in less than O(n^2) time. If yes, how?
Quest-2: What if the given array is not sorted? What will be the time complexity in this case?
Thanks in advance.
How big are the numbers?
If the numbers are of order 106 then we can precompute their divisors in O(MAXlog(MAX)) where MAX is the largest number in the array. We can do so by regular sieves.
Then we can iterate over j and keep a track of count of all elements with indices < j (what values i can take, a prefix count array) and count of all elements with index > j (what values k can take, a suffix count array).
We update these count arrays as we move along the index j. At each index j, we subtract a[j] from target, let this number be X. Then we iterate over divisors of X and check how many divisors we have in prefix and suffix counts we are maintaining.
The complexity of this solution will be O(MAXlog(MAX) + N * MAX1 / 3) Since number of divisors of X are bound by X1 / 3.
This method won't work if the elements in the array can be larger
Nice solution @pleasant.
Yes the numbers are in range [1,10^6].
So basically we are precomputing all the factors and after that we will iterate our main array. And at any point lets say j, we will have Y=target-a[j]. Now we just need to check the divisors of the Y in prefix and suffix array, and we put the number of triplets like ans+=(Number of factors of Y in prefix subarray)+(Number of factors of Y in suffix subarray).
Yes just reiterating the final part. Suppose X(as described in initial comment) is 6 for a certain j. Then we can update final answer as Ans + = prefcnt[1] * suffcnt[6] + prefcnt[2] * suffcnt[3] + prefcnt[3] * suffcnt[2] + prefcnt[6] * suffcnt[1].
After this we increment the count of arr[j] in prefix array and decrement its count in suffix array
Edit: I misunderstood the problem, however this solution does fit if the input array is sorted.
If all values in the array are positive then the following solution works in
:
To make things easier we will insert all values in a map, counting for each value its frequency. We will also denote the target value as X.
Let's suppose 3 positive integers A, B, C that satisfy A * C + B = X and A ≤ B ≤ C. Let's suppose C is a fixed value and we were looking for A, B that satisfy the equation.
If we take the found A and decrease it by Y (positive integer), then we will have to increase B by Y * C to satisfy the equation. B is already positive, so increasing it by Y * C will exceed C, breaking B ≤ C.
Similarly, we can show that increasing A by Y will also lead to a contradiction. So, for a fixed value C there is at most 1 pair A, B that satisfy the wanted equation. Finding such A, B requires just simple maths (divide X by C, etc....).
Now for the solution:
We iterate over the values in the map we made, as we consider the value in each iteration our fixed C. Find the satisfying A, B (if there is such pair). Let's denote Mx as the number of times the value x appears in the input array (can be found quickly in a map). From here it's just a bit of case analysis:
But how are you are accounting for the condition i < j < k. For a fixed C you find out the occurences of A and B that satisfies the condition. But B should come after A. Simply adding MA * MB * MC wont work
Since the array is sorted, if Ai < Aj < Ak (or A < B < C), it must follow that i < j < k
Thanks for the clarification