1
$\begingroup$

We have give positive integer $n$, and we want to find all the pairs $(i, j), i\leq j$ such that: $$i + (i+1) +(i+2)+(i+3)+ \dots + j = n$$

Clearly we can try all possible pairs in $O(N^2)$, but that is pretty slow. Here is my observation.

We already know that the sum of numbers from $1$ to $n$ equals $\frac{n\cdot(n+1)}{2}$. Using simple math we can show that the sum of the numbers in the range from $i$ to $j$ equals $\frac{(j-i+1)\cdot(i+j)}{2}$. If we fix number $i$ using this formula we can find $j$, and check if it is positive integer, but this is $O(N)$, can we go faster?

$\endgroup$
3
$\begingroup$

Another algorithm:

Find all factorizations of $2n$ into a product of two integers, say $2n=r \times s$ with $r \le s$. Then find $i,j$ such that $j-i+1=r$ and $i+j=s$, i.e., $i=(s-r+1)/2$ and $j=(s+r-1)/2$. Check whether $i,j$ are positive. If they are, output this pair $i,j$. Do this for each way of expressing $2n$ as the product $2n=r \times s$.

How do you find all factorizations of $2n$ into two integers? First factor $2n$ into a product of prime powers, say

$$2n = \prod p_i^{e_i}.$$

Next, for each $c_i$ with $0 \le c_i \le e_i$, you can let $r = \prod p_i^{c_i}$ and $s = \prod p_i^{e_i-c_i}$. So in this way you can enumerate all such factorizations. There will be $\prod (1+e_i)$ of them.

The running time for this is significantly faster than $O(n)$. In the worst case the number of such factorizations can be no larger than $O(n^{1/2})$, so the worst-case running time of this method is $O(n^{1/2})$ -- already a significant speedup over Hendrik Jan's elegant answer. Even better, in the average case, the number of such factorizations is far smaller than $n$, exponentially smaller, making this much faster. Often, the dominant cost will be the cost to factor $2n$, which can be done in subexponential time using standard algorithms.

$\endgroup$
  • $\begingroup$ Since one factor is ≤ n^(1/2), the number of factorisations cannot be more than O (n^(1/2)). $\endgroup$ – gnasher729 Oct 14 '17 at 20:51
  • $\begingroup$ Excellent point, @gnasher729, thank you! $\endgroup$ – D.W. Oct 15 '17 at 1:11
1
$\begingroup$

Set $i$ and $j$ to $1$. Set $\mathrm{sum}$ to $0$.

Repeat:

If $\mathrm{sum} = n$ we have a pair, if $\mathrm{sum} < n$ increment $j$ and adjust $\mathrm{sum}$, if $\mathrm{sum} > n$ increment $i$ and adjust $\mathrm{sum}$.

$\endgroup$
  • $\begingroup$ As I can see, this is $O(N)$, can we go anything faster ? $\endgroup$ – someone12321 Oct 14 '17 at 16:03
  • 1
    $\begingroup$ This actually works for the more general 'finding $a_i+a_{i+1}+\cdots+a_j=n$' on positive arrays. $\endgroup$ – Willard Zhan Oct 14 '17 at 18:26
  • $\begingroup$ @WillardZhan You are right of course, so perhaps we can use the fact that $a_i=i$ in a clever way? $\endgroup$ – Hendrik Jan Oct 14 '17 at 20:40

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.