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

0 0 9 minutes read

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 zambiatek!