Get the consecutive numbers whose sum matches with given number

Question

I was going through a simple program that takes a number and finds the number of occurrences of consecutive numbers that matches with given number.

For example:

if input is 15, then the consecutive numbers that sum upto 15 are:

1,2,3,4,5
4,5,6
7,8

So the answer is 3 as we have 3 possibilities here.

When I was looking for a solution I found out below answer:

static long process(long input) {
    long count = 0;
    for (long j = 2; j < input/ 2; j++) {
        long temp = (j * (j + 1)) / 2;
        if (temp > input) {
            break;
        }

        if ((input- temp) % j == 0) {
            count++;
        }
    }
    return count;
}

I am not able to understand how this solves the requirement because this program is using some formula which I am not able to understand properly, below are my doubts:

• The for loop starts from 2, what is the reason for this?
• long temp = (j * (j + 1)) / 2; What does this logic indicates? How is this helpful to solving the problem?
• if ((num - temp) % j == 0) Also what does this indicate?

Please help me in understanding this solution.

Answer 1

I will try to explain this as simple as possible.

If input is 15, then the consecutive numbers that sum upto 15 are:

{1,2,3,4,5} -> 5 numbers
{4,5,6} -> 3 numbers
{7,8} -> 2 numbers

At worst case, this must be less than the Sum of 1st n natural numbers = (n*(n+1) /2.

So for a number 15, there can never be a combination of 6 consecutive numbers summing up to 15 as the sum of 1st 6 numbers =21 which is greater than 15.

Calculate temp: This is (j*(j+1))/2.

Take an example. Let input = 15. Let j =2.

temp = 2*3/2 = 3; #Meaning 1+2 =3

For a 2-number pair, let the 2 terms be 'a+1' and 'a+2'.(Because we know that the numbers are consecutive.)

Now, according to the question, the sum must add up to the number.

This means 2a+3 =15;

And if (15-3) is divisible by 2, 'a' can be found. a=6 -> a+1=7 and a+2=8

Similarly, let a+1 ,a+2 and a+3 a + 1 + a + 2 + a + 3 = 15 3a + 6 = 15 (15-6) must be divisible by 3.

Finally, for 5 consecutive numbers a+1,a+2,a+3,a+4,a+5 , we have 5a + 15 = 15; (15-15) must be divisible by 5.

So, the count will be changed for j =2,3 and 5 when the input is 15

If the loop were to start from 1, then we would be counting 1 number set too -> {15} which is not needed

To summarize:

1) The for loop starts from 2, what is the reason for this?

We are not worried about 1-number set here.

2) long temp = (j * (j + 1)) / 2; What does this logic indicates? How is this helpful to solving the problem?

This is because of the sum of 1st n natural numbers property as I have explained the above by taking a+1 and a+2 as 2 consecutive numbers.

3) if ((num - temp) % j == 0) Also what does this indicate?

This indicates the logic that the input subtracted from the sum of 1st j natural numbers must be divisible by j.

Answer 2

We are looking for consecutive numbers that sum up to the given number. It's quite obvious that there could be at most one series with a given length, so basically we are looking for those values witch could be the length of such a series. variable 'j' is the tested length. It starts from 2 because the series must be at least 2 long. variable 'temp' is the sum of a arithmetic progression from 1 to 'j'.

If there is a proper series then let X the first element. In this case 'input' = j*(X-1) + temp. (So if temp> input then we finished)

At the last line it checks if there is an integer solution of the equation. If there is, then increase the counter, because there is a series with j element which is a solution.

Actually the solution is wrong, because it won't find solution if input = 3. (It will terminate immediately.) the cycle should be:

for(long j=2;;j++)

The other condition terminates the cycle faster anyway.