Pairwise sum and divide

Question

I came across a programming task.

Given an array of integer numbers $A\mid A_i\in\mathbb{N}$, one needs to calculate the sum: $$S=\sum_{i=1}^{N}\sum_{j=i+1}^{N}\left\lfloor\frac{A_i+A_j}{A_i\cdot A_j}\right\rfloor$$ It is the summation of the floor integer values of the fraction $\frac{A_i+A_j}{A_i\cdot A_j}$. $N$ is the length of the array.

In order to compute this faster, one needs to simplify the expression above. I found the corresponding solution code (Python 3):

from collections import Counter
for _ in range(int(input())):
    n, A = int(input()), Counter(map(int, input().split()))
    print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))

which suggests that $$S=\left\lfloor\frac{N_2\cdot\left(N_2-1\right)}{2}\right\rfloor+N_1\cdot\left(N-1\right)$$

$N_1$ is the frequency of $1$ in the array $A$ and $N_2$ the frequency of $2$ in $A$.

How could one obtain this solution?

Answer 1

Note that $$ S = \sum_{i=1}^N\sum_{j=i+1}^N \left\lfloor \frac {1}{A_i} + \frac{1}{A_j} \right \rfloor = \sum_{1 \leq i < j \leq n} \left\lfloor \frac {1}{A_i} + \frac{1}{A_j} \right\rfloor $$ That is, for every pair of $A_i$, we calculate $f(i,j) = \left\lfloor\frac {1}{A_i} + \frac{1}{A_j} \right\rfloor$, and we add up the results.

Note that $f(i,j)$ is non-zero iff one of $A_i$ or $A_j$ is $1$, or $A_i = A_j = 2$. If $A_i = A_j = 1$, then $f(i,j) = 2$.

If there are $N_1$ $A_i$'s that equal $1$, then how many pairs satisfy $A_i = A_j = 1$? The answer is $\binom{N_1}{2} = \frac{N_1(N_1 - 1)}{2}$, which means that the resulting $f(i,j)$ add up to $N_1(N_1 - 1)$.

How many pairs contain one $1$ and one other value? The answer here is $N_1 \cdot (N - N_1)$. The resulting $f(i,j)$ add up to $N_1 \cdot (N - N_1)$.

How many pairs consist of two $2$s? The answer is $\binom {N_2}{2} = \frac{N_2(N_2 - 1)}{2}$. The resulting $f$s add up to $\frac{N_2(N_2 - 1)}{2}$.

Our total sum, then, is $$ N_1(N_1 - 1) + N_1 \cdot (N - N_1) + \frac{N_2(N_2 - 1)}{2} = \\ N_1(N-1) + \frac{N_2(N_2 - 1)}{2} $$ as desired.

NOTE: $\frac{N_2(N_2 - 1)}{2}$ will always be an integer; there's no need to apply the floor function.