Data Modelling & AI Data Structure & Algorithm

Smallest value of N such that the sum of all natural numbers from K to N is at least X

24 June 2025

0

Given two positive integers X and K, the task is to find the minimum value of N possible such that the sum of all natural numbers from the range [K, N] is at least X. If no possible value of N exists, then print -1.

Examples:

Input: K = 5, X = 13
Output: 7
Explanation: The minimum possible value is 7. Sum = 5 + 6 + 7 = 18, which is at least 13.

Input: K = 3, X = 15
Output: 6

Naive Approach: The simplest approach to solve this problem is to check for every value in the range [K, X] and return the first value from this range which has sum of the first N natural numbers at least X.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum possible
// value of N such that sum of natural
// numbers from K to N is at least X
void minimumNumber(int K, int X)
{
    // If K is greater than X
    if (K > X) {
        cout << "-1";
        return;
    }
 
    // Stores value of minimum N
    int ans = 0;
 
    // Stores the sum of values
    // over the range [K, ans]
    int sum = 0;
 
    // Iterate over the range [K, N]
    for (int i = K; i <= X; i++) {
 
        sum += i;
 
        // Check if sum of first i
        // natural numbers is >= X
        if (sum >= X) {
            ans = i;
            break;
        }
    }
 
    // Print the possible value of ans
    cout << ans;
}
 
// Driver Code
int main()
{
    int K = 5, X = 13;
    minimumNumber(K, X);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to find the minimum possible
// value of N such that sum of natural
// numbers from K to N is at least X
static void minimumNumber(int K, int X)
{
     
    // If K is greater than X
    if (K > X) 
    {
        System.out.println("-1");
        return;
    }
 
    // Stores value of minimum N
    int ans = 0;
 
    // Stores the sum of values
    // over the range [K, ans]
    int sum = 0;
 
    // Iterate over the range [K, N]
    for(int i = K; i <= X; i++) 
    {
        sum += i;
 
        // Check if sum of first i
        // natural numbers is >= X
        if (sum >= X) 
        {
            ans = i;
            break;
        }
    }
 
    // Print the possible value of ans
    System.out.println(ans);
}
 
// Driver Code
public static void main(String[] args)
{
    int K = 5, X = 13;
     
    minimumNumber(K, X);
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for the above approach
 
# Function to find the minimum possible
# value of N such that sum of natural
# numbers from K to N is at least X
def minimumNumber(K, X):
     
    # If K is greater than X
    if (K > X):
        print("-1")
        return
 
    # Stores value of minimum N
    ans = 0
 
    # Stores the sum of values
    # over the range [K, ans]
    sum = 0
 
    # Iterate over the range [K, N]
    for i in range(K, X + 1):
        sum += i
 
        # Check if sum of first i
        # natural numbers is >= X
        if (sum >= X):
            ans = i
            break
 
    # Print the possible value of ans
    print(ans)
 
# Driver Code
K = 5
X = 13
 
minimumNumber(K, X)
 
# This code is contributed by subham348

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the minimum possible
// value of N such that sum of natural
// numbers from K to N is at least X
static void minimumNumber(int K, int X)
{
     
    // If K is greater than X
    if (K > X) 
    {
        Console.Write("-1");
        return;
    }
 
    // Stores value of minimum N
    int ans = 0;
 
    // Stores the sum of values
    // over the range [K, ans]
    int sum = 0;
 
    // Iterate over the range [K, N]
    for(int i = K; i <= X; i++) 
    {
        sum += i;
 
        // Check if sum of first i
        // natural numbers is >= X
        if (sum >= X) 
        {
            ans = i;
            break;
        }
    }
 
    // Print the possible value of ans
    Console.Write(ans);
}
 
// Driver Code
public static void Main()
{
    int K = 5, X = 13;
 
    minimumNumber(K, X);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find the minimum possible
// value of N such that sum of natural
// numbers from K to N is at least X
function minimumNumber(K, X)
{
    // If K is greater than X
    if (K > X) {
        document.write("-1");
        return;
    }
 
    // Stores value of minimum N
    let ans = 0;
 
    // Stores the sum of values
    // over the range [K, ans]
    let sum = 0;
 
    // Iterate over the range [K, N]
    for (let i = K; i <= X; i++) {
 
        sum += i;
 
        // Check if sum of first i
        // natural numbers is >= X
        if (sum >= X) {
            ans = i;
            break;
        }
    }
 
    // Print the possible value of ans
    document.write(ans);
}
 
// Driver Code
    let K = 5, X = 13;
    minimumNumber(K, X);
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Output:

Time Complexity: O(N – K)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized by using Binary Search. Follow the steps below to solve the given problem:

Initialize a variable, say res as -1, to store the smallest possible value of N that satisfies the given conditions.
Initialize two variables, say low as K, and high as X, and perform Binary Search on this range by performing the following steps:
- Find the value of mid as low + (high – low) / 2.
- If the sum of natural numbers from K to mid is greater than or equal to X or not.
- If found to be true, then update res as mid and set high = (mid – 1). Otherwise, update the low to (mid + 1).
After completing the above steps, print the value of res as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the sum of
// natural numbers from K to N is >= X
bool isGreaterEqual(int N, int K, int X)
{
    return ((N * 1LL * (N + 1) / 2)
            - ((K - 1) * 1LL * K / 2))
           >= X;
}
 
// Function to find the minimum value
// of N such that the sum of natural
// numbers from K to N is at least X
void minimumNumber(int K, int X)
{
    // If K is greater than X
    if (K > X) {
        cout << "-1";
        return;
    }
 
    int low = K, high = X, res = -1;
 
    // Perform the Binary Search
    while (low <= high) {
        int mid = low + (high - low) / 2;
 
        // If the sum of the natural
        // numbers from K to mid is atleast X
        if (isGreaterEqual(mid, K, X)) {
 
            // Update res
            res = mid;
 
            // Update high
            high = mid - 1;
        }
 
        // Otherwise, update low
        else
            low = mid + 1;
    }
 
    // Print the value of
    // res as the answer
    cout << res;
}
 
// Driver Code
int main()
{
    int K = 5, X = 13;
    minimumNumber(K, X);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to check if the sum of
// natural numbers from K to N is >= X
static boolean isGreaterEqual(int N, int K, int X)
{
    return ((N * 1L * (N + 1) / 2) - 
           ((K - 1) * 1L * K / 2)) >= X;
}
 
// Function to find the minimum value
// of N such that the sum of natural
// numbers from K to N is at least X
static void minimumNumber(int K, int X)
{
     
    // If K is greater than X
    if (K > X)
    {
        System.out.println("-1");
        return;
    }
 
    int low = K, high = X, res = -1;
 
    // Perform the Binary Search
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
 
        // If the sum of the natural
        // numbers from K to mid is atleast X
        if (isGreaterEqual(mid, K, X))
        {
             
            // Update res
            res = mid;
 
            // Update high
            high = mid - 1;
        }
 
        // Otherwise, update low
        else
            low = mid + 1;
    }
 
    // Print the value of
    // res as the answer
    System.out.println(res);
}
 
// Driver Code
public static void main(String[] args)
{
    int K = 5, X = 13;
     
    minimumNumber(K, X);
}
}
 
// This code is contributed by Kingash

Python3

# Python program for the above approach
 
# Function to check if the sum of
# natural numbers from K to N is >= X
 
 
def isGreaterEqual(N, K, X):
    return (((N * (N + 1) // 2)
             - ((K - 1) * K // 2))
            >= X)
 
# Function to find the minimum value
# of N such that the sum of natural
# numbers from K to N is at least X
 
 
def minimumNumber(K, X):
    # If K is greater than X
    if (K > X):
        print("-1")
        return
 
    low = K
    high = X
    res = -1
 
    # Perform the Binary Search
    while (low <= high):
        mid = low + ((high - low) // 2)
 
        # If the sum of the natural
        # numbers from K to mid is atleast X
        if (isGreaterEqual(mid, K, X)):
 
            # Update res
            res = mid
 
            # Update high
            high = mid - 1
 
        # Otherwise, update low
        else:
            low = mid + 1
 
    # Print the value of
    # res as the answer
    print(res)
 
 
# Driver Code
K = 5
X = 13
minimumNumber(K, X)

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to check if the sum of
// natural numbers from K to N is >= X
static bool isGreaterEqual(int N, int K, int X)
{
    return ((N * 1L * (N + 1) / 2) - 
           ((K - 1) * 1L * K / 2)) >= X;
}
 
// Function to find the minimum value
// of N such that the sum of natural
// numbers from K to N is at least X
static void minimumNumber(int K, int X)
{
 
    // If K is greater than X
    if (K > X) 
    {
        Console.Write("-1");
        return;
    }
 
    int low = K, high = X, res = -1;
 
    // Perform the Binary Search
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
 
        // If the sum of the natural
        // numbers from K to mid is atleast X
        if (isGreaterEqual(mid, K, X))
        {
             
            // Update res
            res = mid;
 
            // Update high
            high = mid - 1;
        }
 
        // Otherwise, update low
        else
            low = mid + 1;
    }
 
    // Print the value of
    // res as the answer
    Console.WriteLine(res);
}
 
// Driver Code
public static void Main()
{
    int K = 5, X = 13;
 
    minimumNumber(K, X);
}
}
 
// This code is contributed by subham348

Javascript

<script>
// Javascript program for the above approach
 
// Function to check if the sum of
// natural numbers from K to N is >= X
function isGreaterEqual(N, K, X)
{
    return ((N * parseInt((N + 1) / 2))
            - ((K - 1) * parseInt(K / 2)))
           >= X;
}
 
// Function to find the minimum value
// of N such that the sum of natural
// numbers from K to N is at least X
function minimumNumber(K, X)
{
    // If K is greater than X
    if (K > X) {
        document.write("-1");
        return;
    }
 
    let low = K, high = X, res = -1;
 
    // Perform the Binary Search
    while (low <= high) {
        let mid = low + parseInt((high - low) / 2);
 
        // If the sum of the natural
        // numbers from K to mid is atleast X
        if (isGreaterEqual(mid, K, X)) {
 
            // Update res
            res = mid;
 
            // Update high
            high = mid - 1;
        }
 
        // Otherwise, update low
        else
            low = mid + 1;
    }
 
    // Print the value of
    // res as the answer
    document.write(res);
}
 
// Driver Code
let K = 5, X = 13;
minimumNumber(K, X);
 
// This code is contributed by subham348.
</script>

Output:

Time Complexity: O(log(X – K))
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!

Smallest value of N such that the sum of all natural numbers from K to N is at least X

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

The Razer Kishi V3 hits a record low price and comes with a $30 Amazon credit

Best Android VPN in 2025

Over 30,000 Malicious IPs Target Microsoft Remote Desktop in Global Surge by Husain Parvez

Cyber Threat-Sharing Law Nears Expiration: Experts Warn of Risks by Husain Parvez

EDITOR PICKS

The Razer Kishi V3 hits a record low price and comes with a $30 Amazon credit

Best Android VPN in 2025

Over 30,000 Malicious IPs Target Microsoft Remote Desktop in Global Surge by Husain Parvez

POPULAR POSTS

The Razer Kishi V3 hits a record low price and comes with a $30 Amazon credit

Best Android VPN in 2025

Over 30,000 Malicious IPs Target Microsoft Remote Desktop in Global Surge by Husain Parvez

POPULAR CATEGORY

ABOUT US

FOLLOW US