Find K consecutive integers such that their sum is N

0 0 4 minutes read

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 – $\frac{Number of Terms}{2} * (first Term + Last Term)$
=> $N = \frac{a_1 + a_K}{2} * K$
Solving the equation further to get the first term possible
=> $a_1 + a_K = \frac{2*N}{K}$
Here a_K is the K^th term which can be written as a₁ + K – 1
=> $2*a_1 + K - 1 = \frac{2*N}{K}$
=> $a_1 = \frac{\frac{2*N}{K} + 1 - K}{2}$
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 consecutive
void 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 Code
int 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 integer
class GFG{
 
// Function to check if a number can be
// expressed as the sum of k consecutive
static 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 Code
public 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 integer
using System;
class GFG{
 
// Function to check if a number can be
// expressed as the sum of k consecutive
static 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 Code
public 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 zambiatek!