# Print all possible sums of consecutive numbers with sum N

Given a number N. The task is to print all possible sums of consecutive numbers that add up to N.

Examples :

```Input : 100
Output :
9 10 11 12 13 14 15 16
18 19 20 21 22

Input :125
Output :
8 9 10 11 12 13 14 15 16 17
23 24 25 26 27
62 63
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

One important fact is we can not find consecutive numbers above N/2 that adds up to N, because N/2 + (N/2 + 1) would be more than N. So we start from start = 1 till end = N/2 and check for every consecutive sequence whether it adds up to N or not. If it is then we print that sequence and start looking for the next sequence by incrementing start point.

## C++

 `// C++ program to print consecutive sequences ` `// that add to a given value ` `#include ` `using` `namespace` `std; ` ` `  `void` `findConsecutive(``int` `N) ` `{ ` `    ``// Note that we don't ever have to sum ` `    ``// numbers > ceil(N/2) ` `    ``int` `start = 1, end = (N+1)/2; ` ` `  `    ``// Repeat the loop from bottom to half ` `    ``while` `(start < end) ` `    ``{ ` `        ``// Check if there exist any sequence ` `        ``// from bottom to half which adds up to N ` `        ``int` `sum = 0; ` `        ``for` `(``int` `i = start; i <= end; i++) ` `        ``{ ` `            ``sum = sum + i; ` ` `  `            ``// If sum = N, this means consecutive ` `            ``// sequence exists ` `            ``if` `(sum == N) ` `            ``{ ` `                ``// found consecutive numbers! print them ` `                ``for` `(``int` `j = start; j <= i; j++) ` `                    ``printf``(``"%d "``, j); ` ` `  `                ``printf``(````" "````); ` `                ``break``; ` `            ``} ` ` `  `            ``// if sum increases N then it can not exist ` `            ``// in the consecutive sequence starting from ` `            ``// bottom ` `            ``if` `(sum > N) ` `                ``break``; ` `        ``} ` `        ``sum = 0; ` `        ``start++; ` `    ``} ` `} ` ` `  `// Driver code ` `int` `main(``void``) ` `{ ` `    ``int` `N = 125; ` `    ``findConsecutive(N); ` `    ``return` `0; ` `} `

## Java

 `// Java program to print  ` `// consecutive sequences  ` `// that add to a given value ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `static` `void` `findConsecutive(``int` `N) ` `{ ` `    ``// Note that we don't  ` `    ``// ever have to sum ` `    ``// numbers > ceil(N/2) ` `    ``int` `start = ``1``; ` `    ``int` `end = (N + ``1``) / ``2``; ` ` `  `    ``// Repeat the loop ` `    ``// from bottom to half ` `    ``while` `(start < end) ` `    ``{ ` `        ``// Check if there exist  ` `        ``// any sequence from  ` `        ``// bottom to half which ` `        ``// adds up to N ` `        ``int` `sum = ``0``; ` `        ``for` `(``int` `i = start; i <= end; i++) ` `        ``{ ` `            ``sum = sum + i; ` ` `  `            ``// If sum = N, this means  ` `            ``// consecutive sequence exists ` `            ``if` `(sum == N) ` `            ``{ ` `                ``// found consecutive  ` `                ``// numbers! print them ` `                ``for` `(``int` `j = start; j <= i; j++) ` `                     `  `                    ``System.out.print(j + ``" "``); ` `                    ``System.out.println(); ` `                ``break``; ` `            ``} ` ` `  `            ``// if sum increases N then ` `            ``// it can not exist in the  ` `            ``// consecutive sequence  ` `            ``// starting from bottom ` `            ``if` `(sum > N) ` `                ``break``; ` `        ``} ` `        ``sum = ``0``; ` `        ``start++; ` `    ``} ` `} ` ` `  `// Driver code ` `public` `static` `void` `main (String[] args) ` `{ ` `    ``int` `N = ``125``; ` `    ``findConsecutive(N); ` `} ` `} ` ` `  `// This code is contributed by m_kit `

## Python3

 `# Python3 program to print consecutive  ` `# sequences that add to a given value ` `def` `findConsecutive(N): ` ` `  `    ``# Note that we don't ever have to  ` `    ``# Sum numbers > ceil(N/2) ` `    ``start ``=` `1` `    ``end ``=` `(N ``+` `1``) ``/``/` `2` ` `  `    ``# Repeat the loop from bottom to half ` `    ``while` `(start < end): ` `     `  `        ``# Check if there exist any sequence ` `        ``# from bottom to half which adds up to N ` `        ``Sum` `=` `0` `        ``for` `i ``in` `range``(start, end ``+` `1``): ` `         `  `            ``Sum` `=` `Sum` `+` `i ` ` `  `            ``# If Sum = N, this means consecutive ` `            ``# sequence exists ` `            ``if` `(``Sum` `=``=` `N): ` `             `  `                ``# found consecutive numbers! prthem ` `                ``for` `j ``in` `range``(start, i ``+` `1``): ` `                    ``print``(j, end ``=` `" "``) ` ` `  `                ``print``() ` `                ``break` ` `  `            ``# if Sum increases N then it can not ` `            ``# exist in the consecutive sequence  ` `            ``# starting from bottom ` `            ``if` `(``Sum` `> N): ` `                ``break` `         `  `        ``Sum` `=` `0` `        ``start ``+``=` `1` `     `  `# Driver code ` `N ``=` `125` `findConsecutive(N) ` ` `  `# This code is contributed by Mohit kumar 29 `

## C#

 `// C# program to print  ` `// consecutive sequences  ` `// that add to a given value ` `using` `System; ` ` `  `class` `GFG ` `{ ` `static` `void` `findConsecutive(``int` `N) ` `{ ` `    ``// Note that we don't  ` `    ``// ever have to sum ` `    ``// numbers > ceil(N/2) ` `    ``int` `start = 1; ` `    ``int` `end = (N + 1) / 2; ` ` `  `    ``// Repeat the loop ` `    ``// from bottom to half ` `    ``while` `(start < end) ` `    ``{ ` `        ``// Check if there exist  ` `        ``// any sequence from  ` `        ``// bottom to half which ` `        ``// adds up to N ` `        ``int` `sum = 0; ` `        ``for` `(``int` `i = start; i <= end; i++) ` `        ``{ ` `            ``sum = sum + i; ` ` `  `            ``// If sum = N, this means  ` `            ``// consecutive sequence exists ` `            ``if` `(sum == N) ` `            ``{ ` `                ``// found consecutive  ` `                ``// numbers! print them ` `                ``for` `(``int` `j = start; j <= i; j++) ` `                     `  `                    ``Console.Write(j + ``" "``); ` `                    ``Console.WriteLine(); ` `                ``break``; ` `            ``} ` ` `  `            ``// if sum increases N then ` `            ``// it can not exist in the  ` `            ``// consecutive sequence  ` `            ``// starting from bottom ` `            ``if` `(sum > N) ` `                ``break``; ` `        ``} ` `        ``sum = 0; ` `        ``start++; ` `    ``} ` `} ` ` `  `// Driver code ` `static` `public` `void` `Main () ` `{ ` `    ``int` `N = 125; ` `    ``findConsecutive(N); ` `} ` `} ` ` `  `// This code is contributed by ajit `

## PHP

 ` ceil(N/2) ` `    ``\$start` `= 1; ` `    ``\$end` `= (``\$N` `+ 1) / 2; ` ` `  `    ``// Repeat the loop from ` `    ``// bottom to half ` `    ``while` `(``\$start` `< ``\$end``) ` `    ``{ ` `        ``// Check if there exist any  ` `        ``// sequence from bottom to  ` `        ``// half which adds up to N ` `        ``\$sum` `= 0; ` `        ``for` `(``\$i` `= ``\$start``; ``\$i` `<= ``\$end``; ``\$i``++) ` `        ``{ ` `            ``\$sum` `= ``\$sum` `+ ``\$i``; ` ` `  `            ``// If sum = N, this means  ` `            ``// consecutive sequence exists ` `            ``if` `(``\$sum` `== ``\$N``) ` `            ``{ ` `                ``// found consecutive  ` `                ``// numbers! print them ` `                ``for` `(``\$j` `= ``\$start``; ``\$j` `<= ``\$i``; ``\$j``++) ` `                    ``echo` `\$j` `,``" "``; ` ` `  `                ``echo` ```" "````; ` `                ``break``; ` `            ``} ` ` `  `            ``// if sum increases N then it  ` `            ``// can not exist in the consecutive  ` `            ``// sequence starting from bottom ` `            ``if` `(``\$sum` `> ``\$N``) ` `                ``break``; ` `        ``} ` `        ``\$sum` `= 0; ` `        ``\$start``++; ` `    ``} ` `} ` ` `  `// Driver code ` `\$N` `= 125; ` `findConsecutive(``\$N``); ` ` `  `// This code is contributed by ajit ` `?> `

Output :

```8 9 10 11 12 13 14 15 16 17
23 24 25 26 27
62 63
```

Optimized Solution:
In above solution, we keep recalculating sums from start to end, which results in O(N^2) worst case time complexity. This can be avoided by using a precomputed array of sums, or better yet – just keeping track of the sum you have so far and adjusting it depending on how it compares to the desired sum.

Time complexity of below code is O(N).

## C++

 `// Optimized C++ program to find sequences of all consecutive ` `// numbers with sum equal to N ` `#include ` ` `  `void` `printSums(``int` `N) ` `{ ` `    ``int` `start = 1, end = 1; ` `    ``int` `sum = 1; ` ` `  `    ``while` `(start <= N/2) ` `    ``{ ` `        ``if` `(sum < N) ` `        ``{ ` `            ``end += 1; ` `            ``sum += end; ` `        ``} ` `        ``else` `if` `(sum > N) ` `        ``{ ` `            ``sum -= start; ` `            ``start += 1; ` `        ``} ` `        ``else` `if` `(sum == N) ` `        ``{ ` `            ``for` `(``int` `i = start; i <= end; ++i) ` `                ``printf``(``"%d "``, i); ` ` `  `            ``printf``(````" "````); ` `            ``sum -= start; ` `            ``start += 1; ` `        ``} ` `    ``} ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``printSums(125); ` `    ``return` `0; ` `} `

## Java

 `// Optimized Java program to find ` `// sequences of all consecutive ` `// numbers with sum equal to N ` `import` `java.io.*; ` ` `  `class` `GFG { ` `     `  `    ``static` `void` `printSums(``int` `N) ` `    ``{ ` `        ``int` `start = ``1``, end = ``1``; ` `        ``int` `sum = ``1``; ` `     `  `        ``while` `(start <= N/``2``) ` `        ``{ ` `            ``if` `(sum < N) ` `            ``{ ` `                ``end += ``1``; ` `                ``sum += end; ` `            ``} ` `            ``else` `if` `(sum > N) ` `            ``{ ` `                ``sum -= start; ` `                ``start += ``1``; ` `            ``} ` `            ``else` `if` `(sum == N) ` `            ``{ ` `                ``for` `(``int` `i = start;  ` `                         ``i <= end; ++i) ` `                          `  `                    ``System.out.print(i  ` `                                ``+ ``" "``); ` `     `  `                ``System.out.println(); ` `                ``sum -= start; ` `                ``start += ``1``; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` `            ``printSums(``125``); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## C#

 `// Optimized C# program to find ` `// sequences of all consecutive ` `// numbers with sum equal to N ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``static` `void` `printSums(``int` `N) ` `    ``{ ` `        ``int` `start = 1, end = 1; ` `        ``int` `sum = 1; ` `     `  `        ``while` `(start <= N/2) ` `        ``{ ` `            ``if` `(sum < N) ` `            ``{ ` `                ``end += 1; ` `                ``sum += end; ` `            ``} ` `            ``else` `if` `(sum > N) ` `            ``{ ` `                ``sum -= start; ` `                ``start += 1; ` `            ``} ` `            ``else` `if` `(sum == N) ` `            ``{ ` `                ``for` `(``int` `i = start;  ` `                        ``i <= end; ++i) ` `                         `  `                    ``Console.Write(i  ` `                                ``+ ``" "``); ` `     `  `                ``Console.WriteLine(); ` `                ``sum -= start; ` `                ``start += 1; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `Main () ` `    ``{ ` `            ``printSums(125); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 ` ``\$N``) ` `        ``{ ` `            ``\$sum` `-= ``\$start``; ` `            ``\$start` `+= 1; ` `        ``} ` `        ``else` `if` `(``\$sum` `== ``\$N``) ` `        ``{ ` `            ``for` `(``\$i` `= ``\$start``; ``\$i` `<= ``\$end``; ++``\$i``) ` `                ``echo` `\$i``,``" "``; ` `                ``echo` ```" "````; ` `            ``\$sum` `-= ``\$start``; ` `            ``\$start` `+= 1; ` `        ``} ` `    ``} ` `} ` ` `  `// Driver Code ` `    ``printSums(125); ` ` `  `// This code is contributed by jit_t ` `?> `

Output :

```8 9 10 11 12 13 14 15 16 17
23 24 25 26 27
62 63
```