Smallest value of N such that the sum of all natural numbers from K to N is at least X
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> |
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 >= 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> |
7
Time Complexity: O(log(X – K))
Auxiliary Space: O(1)
Contact Us