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<bits/stdc++.h> 
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

<?php 
// PHP program to print consecutive  
// sequences that add to a given value 
  
function 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 = $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 <stdio.h> 
  
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

<?php 
// Optimized PHP program to find  
// sequences of all consecutive 
// numbers with sum equal to N 
  
function printSums($N) 
{ 
    $start = 1; $end = 1; 
    $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 ($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

Reference :
https://www.careercup.com/page?pid=microsoft-interview-questions&n=2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Print all possible sums of consecutive numbers with sum N

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

C++

Java

Python3

C#

PHP

C++

Java

C#

PHP

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books