1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The original page does not specify what sort of numbers are in $A$. You say they are integers, but they have to be positive integers. $\endgroup$ – Ross Millikan Aug 17 '16 at 3:42
  • $\begingroup$ @RossMillikan Looking at the original page, in the section "Input Format" and "Constraints" it is clarified that $A$ contains positive integers. Corresponding to this I stated above that $A_i\in \mathbb{N}$. $\endgroup$ – Andy Aug 18 '16 at 16:57
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great explanation! A typo in 4th line: $2$ instead of $\frac{1}{2}$ $\endgroup$ – Andy Aug 16 '16 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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