Print all possible sums of consecutive numbers with sum N in C++

In this problem, we are given a positive integer N and we have to print the sequence of all possible consecutive numbers with a sum equal to N.

Let’s take an example to understand the problem,

Input: N = 15 Output: 1 2 3 4 5 7 8

A simple solution to this problem is by adding up consecutive sequence combinations till N/2. And then print the sequence that sums up to N.

Example

 Live Demo

#include<iostream> using namespace std; void printConsequtiveSum(int N){    int start = 1, end = (N+1)/2;    while (start < end){       int sum = 0;       for (int i = start; i <= end; i++){          sum = sum + i;          if (sum == N){             for (int j = start; j <= i; j++)                cout<<j<<" ";                cout<<endl;                break;          }          if (sum > N)             break;       }       sum = 0;       start++;    } } int main(){    int N = 25;    cout<<"Sequence of consicutive numbers that sum upto "<<N<<" are :\n";    printConsequtiveSum(N);    return 0; }

Output

The sequence of consecutive numbers that sum up to 25 are −

3 4 5 6 7 12 13

This method is easy but is not so efficient.

So, we have a more complex but optimum solution that will be using a precomputed array of sums to keep track of sum. This will decrease the complexity of the sum.

Example

 Live Demo

#include <iostream> using namespace std; void printConsequtiveSum(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)             cout<<i<<" ";             cout<<endl;             sum -= start;             start += 1;       }    } } int main(){    int N = 25;    cout<<"Sequence of consicutive numbers that sum upto "<<N<<" are:\n";    printConsequtiveSum(N);    return 0; }

Output

Sequence of consecutive numbers that sum up to 25 are −

3 4 5 6 7 12 13