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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ConsecutiveNumberSum {

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            int count = 0;
            int sum = Integer.valueOf(br.readLine());

            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());
        }
    }
}



No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...