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.
leave a comment
0 Comments