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 Xvoid 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 Codeint main(){ int K = 5, X = 13; minimumNumber(K, X); return 0;} |
Java
// Java program for the above approachimport 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 Xstatic 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 Codepublic 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 Xdef 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 CodeK = 5X = 13minimumNumber(K, X)# This code is contributed by subham348 |
C#
// C# program for the above approachusing 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 Xstatic 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 Codepublic 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 Xfunction 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:
7
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 >= Xbool 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 Xvoid 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 Codeint main(){ int K = 5, X = 13; minimumNumber(K, X); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to check if the sum of// natural numbers from K to N is >= Xstatic 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 Xstatic 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 Codepublic 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 >= Xdef 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 Xdef 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 CodeK = 5X = 13minimumNumber(K, X) |
C#
// C# program for the above approachusing System;class GFG{// Function to check if the sum of// natural numbers from K to N is >= Xstatic 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 Xstatic 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 Codepublic 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 >= Xfunction 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 Xfunction 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 Codelet K = 5, X = 13;minimumNumber(K, X);// This code is contributed by subham348.</script> |
Output:
7
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
