Given an array A of N integers . I need to find X such that the difference between the following 2 values (A[1] * A[2] * ... * A[X]) and (A[X+1] * A[X+2] * ... * A[N]) is minimum possible i.e. I need to minimize | (A[1] * A[2] * ... * A[X]) - (A[X+1] * A[X+2] * ... * A[N]) | and if there are multiple such values of X, print the smallest one.
Constraints:-
1 <= N <= 10^5
1 <= A[i] <= 10^18.
I am not able to find the approach to solve this problem in efficient way.
What should be the best approach to solve this problem. Is there any special algorithm for multiplying large quantity of numbers.
The idea is to use a form of prefix and suffix products.
Let:
pre[i] = A[1] * A[2] * ... A[i] andsuf[i] = A[i] * A[i + 1] * ... A[N]
You can compute these arrays in O(n) time, as:
Then, iterate from i = 1 to N and compute the maximum of:
abs(pre[i] - suf[i + 1])
Observe that pre[i] - suf[i + 1] is the same as:
(A[1] * A[2] * ... * A[i]) - (A[i + 1] * A[i + 2] ... * A[N])
which is exactly what you want to compute.
You can do it in O(n): first go - get the product of all elements of array (P) and the second go - assuming at start the left part is one and the second is P, on each step i multiply left on X[i] and divide right on X[i]. Continue the process until left is less than right.
Since you have large array of numbers, you need some big-number multiplication. So, maybe you better move to array of logarithms of A[i], LA[i] and move to new criteria.
Edit:
As mentioned by @CiaPan, the precision of standard 64-bit decimal is not enough for making log operation here (since values may be up to 10^18).
So to solve this problem you should first split values of the source array to pairs such that:
s[2*i] = a[i].toDouble / (10.0^9)
s[2*i+1] = a[i]/s[2*i]
Array s is twice longer than source array a, but its values do not exceed 10^9, so it is safe to apply log operation, then find desired sX for array s and divide it to 2 to get X for array a.
Extra-precision logarithm logic is not required.
