Tutorialspoint.dev

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 



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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter