## Wednesday, 3 January 2018

### Algorithms | Number of ways to express a number as sum of consecutive numbers

Given a number N, find the number of ways to represent this number as a sum of 2 or more consecutive natural numbers.

Examples
Input: 11
Output: 1
11 can be represented as:
5+6 = 11

Input: 27
Output: 3
27 can only be represented as:
13+14 = 27
8+9+10 = 27
2+3+4+5+6+7 = 27

n+1 consecutive number can be summed up to get sum N

sum = f + (f+1) + (f+2) + .. + (f+n);
sum = (n+1)/2  * (f + f + n);  // using A.P. formula.
sum = (n+1)/2 * (2 * f + n);
f = sum/(n+1) – n/2;

We substitute the values of n starting from 1 till n*(n+1)/2 < sum
If we get ‘f’ as a natural number then the solution should be counted.

Java code
package com.microsoft;
import java.io.IOException;

public class ConsecutiveNumberSum {

public static void main(String[] args) {

int count = 0;

for (int n = 0; n * (n + 1) / 2 < sum; n++) {

float first = (float) (sum / (n + 1.0) - n / 2.0);

if (first < sum && Math.floor(first) == Math.ceil(first)) {
System.out.println(first);
count++;
}
}
System.out.println(count);
} catch (IOException e) {
System.out.println(e.getMessage());
}
}
}