Given two integers N and K, the task is to find K consecutive integers such that their sum if N.
Note: If there is no such K integers print -1.
Examples:
Input: N = 15, K = 5
Output: 1 2 3 4 5
Explanation:
N can be represented as sum of 5 consecutive integers as follows –
=> N => 1 + 2 + 3 + 4 + 5 = 15
Input: N = 33, K = 6
Output: 3 4 5 6 7 8
Explanation:
N can be represented as sum of 6 consecutive integers as follows –
=> N => 3 + 4 + 5 + 6 + 7 + 8 = 33
Naive Approach: A simple solution is to run a loop from i = 0 to N – (K – 1) to check if K consecutive integers starting from i is having sum as N.
Efficient Approach: The idea is to use Arithmetic Progression to solve this problem, where sum of K terms of arithmetic progression with common difference is 1 can be defined as follows –
- Sum of K Terms –
=>
- Solving the equation further to get the first term possible
=>
- Here aK is the Kth term which can be written as a1 + K – 1
=>
=>
- Finally, check the first term computed is an integer, If yes then K consecutive number exists whose sum if N.
Below is the implementation of the above approach:
C++
// C++ implementation to check if// a number can be expressed as// sum of K consecutive integer#include <bits/stdc++.h>using namespace std;// Function to check if a number can be// expressed as the sum of k consecutivevoid checksum(int n, int k){ // Finding the first // term of AP float first_term = ((2 * n) / k + (1 - k)) / 2.0; // Checking if first // term is an integer if (first_term - int(first_term) == 0) { // Loop to print the K // consecutive integers for (int i = first_term; i <= first_term + k - 1; i++) { cout << i << " "; } } else cout << "-1";}// Driver Codeint main(){ int n = 33, k = 6; checksum(n, k); return 0;} |
Java
// Java implementation to check if// a number can be expressed as// sum of K consecutive integerclass GFG{// Function to check if a number can be// expressed as the sum of k consecutivestatic void checksum(int n, int k){ // Finding the first // term of AP float first_term = (float) (((2 * n) / k + (1 - k)) / 2.0); // Checking if first // term is an integer if (first_term - (int)(first_term) == 0) { // Loop to print the K // consecutive integers for(int i = (int)first_term; i <= first_term + k - 1; i++) { System.out.print(i + " "); } } else System.out.print("-1");}// Driver Codepublic static void main(String[] args){ int n = 33, k = 6; checksum(n, k);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to check # if a number can be expressed as # sum of K consecutive integer # Function to check if a number can be # expressed as the sum of k consecutive def checksum(n, k): # Finding the first # term of AP first_term = ((2 * n) / k + (1 - k)) / 2.0 # Checking if first # term is an integer if (first_term - int(first_term) == 0): # Loop to print the K # consecutive integers for i in range(int(first_term), int(first_term) + k): print(i, end = ' ') else: print('-1')# Driver Code if __name__=='__main__': (n, k) = (33, 6) checksum(n, k)# This code is contributed by rutvik_56 |
C#
// C# implementation to check if// a number can be expressed as// sum of K consecutive integerusing System;class GFG{// Function to check if a number can be// expressed as the sum of k consecutivestatic void checksum(int n, int k){ // Finding the first // term of AP float first_term = (float)(((2 * n) / k + (1 - k)) / 2.0); // Checking if first // term is an integer if (first_term - (int)(first_term) == 0) { // Loop to print the K // consecutive integers for(int i = (int)first_term; i <= first_term + k - 1; i++) { Console.Write(i + " "); } } else Console.Write("-1");}// Driver Codepublic static void Main(String[] args){ int n = 33, k = 6; checksum(n, k);}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// javascript implementation to check if// a number can be expressed as// sum of K consecutive integer // Function to check if a number can be// expressed as the sum of k consecutive function checksum(n , k) { // Finding the first // term of AP var first_term = (((2 * n) / k + (1 - k)) / 2.0); // Checking if first // term is an integer if (first_term - parseInt( (first_term)) == 0) { // Loop to print the K // consecutive integers for (i = parseInt( first_term); i <= first_term + k - 1; i++) { document.write(i + " "); } } else document.write("-1"); } // Driver Code var n = 33, k = 6; checksum(n, k);// This code contributed by Rajput-Ji</script> |
Output:
3 4 5 6 7 8
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!