Provide an $O(k)$ algorithm to find $k$- magic pairs of positive integers a and b of type signed int where a magic pair is defined as $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $. You can't use the summation formula $\frac{N \cdot (N+1)}{2}$ as it would result in an overflow. Even you can't run sums such as sum1 and sum2, it's still going to overflow.

Example: (6,8) (35,49) (204,288) are the first three Magic Pairs.
P.C: This was our recent examination question, I am curious to know the algorithm.

  • $\begingroup$ Your formulas are not well formed? Do you mean $\sum_{i=1}^{a-1} i$? Also "of type signed int" doesn't say much about the range of the integers as the maximum value representable by a signed int varies across languages and architectures. $\endgroup$ – Steven Nov 26 '19 at 9:55
  • $\begingroup$ @Steven It meant that while writing a program we can't directly use the formula for summation or run two sums from 1 to $a-1$ and $a+1$ to $b$ and compare them, which on doing so, leads to integer overflow. I Hope the question is clear now! $\endgroup$ – Akash Tadwai Nov 26 '19 at 9:58
  • $\begingroup$ What computational complexity are you aiming for? $\endgroup$ – Steven Nov 26 '19 at 10:04

There are different ways you can use to solve that problem.

One simple but inefficient solution is just that of just computing the two sums in parallel while only keeping track of the difference between their partial sums. I.e., if you added the first $x$ terms of the first sum and first $y$ terms of the second sum, then you'll only remember $x$, $y$, and $\Delta = \sum_{i=1}^x i - \sum_{k=a+1}^{a+1+y} k$. If $\Delta$ is non-positive, then consider the next term of the first sum (i.e., increment $x$ by one and add $x$ to $\Delta$). If $\Delta$ is positive, then consider the next term of the second sum (i.e., increment $y$ by one and subtract $a+1+y$ from $\Delta$). In this way $|\Delta|$ will never exceed $\max\{a,b\}$.

Another more efficient solution is as follows. Using the summation formula you can write: $ \sum_{i=1}^{a-1} i = \frac{a(a-1)}{2} = \frac{b(b+1)}{2} - \frac{a(a+1)}{2} = \sum_{k=a+1}^{b} k$, and some simplifications lead to: $2a^2 = b(b+1)$.

This means that, once you fix $b$, you can find the corresponding value of $a$ as follows: $$ a= \frac{1}{\sqrt{2}} \cdot \sqrt{b} \cdot \sqrt{b+1}. $$

Notice that $\sqrt{b} \cdot \sqrt{b+1}$ must always be greater than $b$ and smaller than $b+1$, meaning that $\frac{b}{\sqrt{2}} < a < \frac{b}{\sqrt{2}} + \frac{1}{\sqrt{2}}$ and, since $\frac{1}{\sqrt{2}} < 1$, there is at most one integer in that interval, namely $ 1+ \left\lfloor \frac{b}{\sqrt{2}} \right\rfloor = 1+ \left\lfloor \frac{\sqrt{2} b}{2} \right\rfloor $.


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.