1
$\begingroup$

Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo $ 10^9 + 7 $

$$ \prod_{i < j} (arr[j] - arr[i]) \% (10^9 + 7) $$

Best approach I can think of is finding frequency of primes in product by grouping elements with same modular residue, which allows $ O(N * M / \log M) $ if $M$ is maximum number in array.

I have considered mathematical ways by polynomial multiplication and divide and conquer, which seems most promising but can't solve completely.

Is there any way to find this for arrays of length upto $ 10^ 5 $, and numbers upto $ 10 ^ 9 $?

$\endgroup$
3
  • $\begingroup$ Where did you encounter this problem? Can you credit the source? $\endgroup$
    – D.W.
    Sep 4, 2023 at 16:40
  • $\begingroup$ @D.W. it's a variation of problem on codeforces which had a smaller modulo (around 1000), that was easy to solve, I don't have link to that problem but solution to that won't help in this variation as it should be independent of modulo. $\endgroup$ Sep 5, 2023 at 3:45
  • $\begingroup$ If I am right, all arithmetic fits in 64 bit integers, and there are $5\cdot10^9$ products and remainders to take. Is the direct approach too slow ? $\endgroup$
    – user16034
    Sep 5, 2023 at 18:49

1 Answer 1

1
$\begingroup$

I think a divide and conquer (D&C) approach is valid, and leads to an $O(n \log^3 n)$ solution (maybe the log exponent can be reduced).

The D&C technique reduces the problem to the following: Given two arrays $A$ and $B$ compute

$$\prod_{a \in A, b \in B} a - b$$

Consider the following polynomial:

$$P_A(X) = \prod_{a \in A} a - X$$

If we can evaluate $P_A$ on every element of $B$, then the product of all those results gives the desired solution. To compute the polynomial $\prod_{a \in A} a - X$ you can use a divide and conquer based algorithm and using polynomial multiplication in $O(n \log n)$ you can compute $P_A$ in $O(n \log^2 n)$.

Once $P_A$ has been computed, you can evaluate it on every element in $B$ in $O(n \log^2 n)$ time see this answer.

Since every step of the D&C problem is solvable in $O(n \log^2 n)$, the whole problem is solvable in $O(n \log^3 n)$.

Note that the computation of $P_A$ can be done recursively in the outer D&C as well, so that part should not impart an extra log factor. Therefore the critical part if you want to reduce the complexity is the multipoint evaluation.

$\endgroup$
1
  • $\begingroup$ For $n=10^5$, the speedup $\dfrac n{\lg^3 n}$ is on the order of $20$. But this does not account for the hidden constants. $\endgroup$
    – user16034
    Sep 6, 2023 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.