1
$\begingroup$

I am trying to understand the question -:

Given a number N, write a function to express N as sum of two or more consecutive positive numbers. If there is no solution, output -1. If there are multiple solution, then print one of them.

Examples:

Input : N = 10 Output : 4 + 3 + 2 + 1

Input : N = 8 Output : -1

Input : N = 24 Output : 9 + 8 + 7

Link

Here I got the explanation.

Sum of first n natural numbers = n * (n + 1)/2

Sum of first (n + k) numbers = (n + k) * (n + k + 1)/2

If N is sum of k consecutive numbers, then
following must be true.

N = [(n+k)(n+k+1) - n(n+1)] / 2

OR 

2 * N = [(n+k)(n+k+1) - n(n+1)]

But the problem arises in the code.

static void findConsecutive(int N)
{
    for (int last=1; last<N; last++)
    {
        for (int first=0; first<last; first++)
        {
            if (2*N == (last-first)*(last+first+1))
            {
                System.out.printf(N + " = ");
                printConsecutive(last, first+1);
                return;
            }
        }
    }
    System.out.print("-1");
}

I am not able to get why it is using

2*N == (last - first) * (last + first + 1);

Please help.

$\endgroup$
  • $\begingroup$ If $N$ has an odd prime factor $p$ it can be expressed as the same of $p$ consecutive integers. Otherwise it is a power of $2$. The integers in the first case need not be positive, though. $\endgroup$ – Mark Bennet Oct 15 '17 at 6:35
  • $\begingroup$ @MarkBennet So what is the relationship between 2*N == (last - first) * (last + first + 1); and your comment? I have the idea of calculating the number of ways. $\endgroup$ – Brij Raj Kishore Oct 15 '17 at 6:43
  • 1
    $\begingroup$ Actually if $first$ is the first of the consecutive integers and $last$ the last, it should be $$\sum_{j=first}^{last} j = last(last+1)/2 - (first-1)(first)/2 = (last+first)(last+1-first)/2$$ $\endgroup$ – Robert Israel Oct 15 '17 at 6:49
  • $\begingroup$ I also thought so. So there it is given wrong. $\endgroup$ – Brij Raj Kishore Oct 15 '17 at 6:55
  • $\begingroup$ @RobertIsrael Please rewrite your comment as answer as this is the valid solution and explanation of my question. $\endgroup$ – Brij Raj Kishore Jun 19 '18 at 4:08
1
$\begingroup$

(As requested, turning the comment into an answer)

Actually if $first$ is the first of the consecutive integers and $last$ the last, it should be $$ \sum_{j=first}^{last} j = last(last+1)/2 - (first-1)(first)/2 = (last+first)(last+1-first)/2 $$

$\endgroup$
1
$\begingroup$

Note that: $$(n+k)(n+k+1) - n(n+1)=2nk+k^2+k=(2n+k+1)k=\\ ((\underbrace{n+k}_{last})+(\underbrace{n+1}_{first}))((\underbrace{n+k}_{last})-(\underbrace{n+1}_{first})+1).\\ $$

$\endgroup$

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.