Maximize X such that sum of numbers in range [1, X] is at most K
Given two integers N and an integer K, the task is to find the count of integers less than or equal to N, such that the sum of the natural numbers up to that integer is less than or equal to K.
Examples:
Input: N = 5, K = 10
Output: 4
Explanation:
The integers 1, 2, 3, and 4 satisfy the condition.
- The sum of natural numbers up to integer 1 is equal to 1. Which is less than 10.
- The sum of natural numbers up to integer 2 is equal to (1+2 =) 3. Which is less than 10.
- The sum of natural numbers up to integer 3 is equal to (1+2+3 =) 6. Which is less than 10.
- The sum of natural numbers up to integer 4 is equal to (1+2+3+4 =) 10. Which is equal to 10.
Input: N=3, K=0
Output: 0
Approach: The simplest approach is to traverse over the range [1, N] and count the number of elements whose sum is less than or equal to K.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the elements with // sum of the first that many natural // numbers less than or equal to K int Count( int N, int K) { // If K equals to 0 if (K == 0) return 0; // Stores sum of first i natural // numbers int sum = 0; // Stores the result int res = 0; // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { // Increment sum by i sum += i; // Is sum is less than or // equal to K if (sum <= K) res++; // Otherwise, else break ; } // Return res return res; } // Driver Code int main() { // Input int N = 6, K = 14; // Function call cout << Count(N, K); return 0; } |
Java
// Java program for the above approach public class GFG { // Function to count the elements with // sum of the first that many natural // numbers less than or equal to K static int Count( int N, int K) { // If K equals to 0 if (K == 0 ) return 0 ; // Stores sum of first i natural // numbers int sum = 0 ; // Stores the result int res = 0 ; // Iterate over the range [1, N] for ( int i = 1 ; i <= N; i++) { // Increment sum by i sum += i; // Is sum is less than or // equal to K if (sum <= K) res++; // Otherwise, else break ; } // Return res return res; } // Driver Code public static void main(String args[]) { // Input int N = 6 , K = 14 ; // Function call System.out.println(Count(N, K)); } } // This code is contributed by SoumikMondal |
Python3
# Python3 program for the above approach # Function to count the elements with # sum of the first that many natural # numbers less than or equal to K def Count(N, K): # If K equals to 0 if (K = = 0 ): return 0 # Stores sum of first i natural # numbers sum = 0 # Stores the result res = 0 # Iterate over the range [1, N] for i in range ( 1 , N + 1 , 1 ): # Increment sum by i sum + = i # Is sum is less than or # equal to K if ( sum < = K): res + = 1 # Otherwise, else : break # Return res return res # Driver Code if __name__ = = '__main__' : # Input N = 6 K = 14 # Function call print (Count(N, K)) # This code is contributed by bgangwar59 |
C#
// C# program for the above approach using System; class GFG { // Function to count the elements with // sum of the first that many natural // numbers less than or equal to K static int Count( int N, int K) { // If K equals to 0 if (K == 0) return 0; // Stores sum of first i natural // numbers int sum = 0; // Stores the result int res = 0; // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { // Increment sum by i sum += i; // Is sum is less than or // equal to K if (sum <= K) res++; // Otherwise, else break ; } // Return res return res; } // Driver Code public static void Main() { // Input int N = 6, K = 14; // Function call Console.WriteLine(Count(N, K)); } } // This code is contributed by subhammahato348. |
Javascript
<script> // Javascript program for the above approach // Function to count the elements with // sum of the first that many natural // numbers less than or equal to K function Count(N, K) { // If K equals to 0 if (K == 0) return 0; // Stores sum of first i natural // numbers let sum = 0; // Stores the result let res = 0; // Iterate over the range [1, N] for (let i = 1; i <= N; i++) { // Increment sum by i sum += i; // Is sum is less than or // equal to K if (sum <= K) res++; // Otherwise, else break ; } // Return res return res; } // Driver Code // Input let N = 6, K = 14; // Function call document.write(Count(N, K)); // This code is contributed by _saurabh_jaiswal. </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using a binary search algorithm. Follow the steps below to solve the problem:
- Initialize a variable say res as 0 to store the result.
- Also, initialize two variables, say low and high, as 1 and N respectively.
- Iterate until low is less than or equal to high and perform the following steps:
- Find the mid-value of the range [low, high] and store it in a variable, say mid.
- Calculate the sum of the natural numbers up to mid and, store it in a variable, say sum.
- If the sum is less than or equal to K, then update res to max(res, mid) and assign mid+1 to low.
- Otherwise, assign mid-1 to high.
- Finally, after completing the above steps, print the value of res as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the elements with // sum of the first that many natural // numbers less than or equal to K int Count( int N, int K) { // If K equals to 0 if (K == 0) return 0; // Stores the result int res = 0; int low = 1, high = N; // Iterate until low is less than // or equal to high while (low <= high) { int mid = (low + high) / 2; // Stores the sum of first mid // natural numbers int sum = (mid * mid + mid) / 2; // If sum is less than or equal // to K if (sum <= K) { // Update res and low res = max(res, mid); low = mid + 1; } // Otherwise, else { // Update high = mid - 1; } } // Return res return res; } // Driver Code int main() { // Input int N = 6, K = 14; // Function call cout << Count(N, K); return 0; } |
Java
// Java program for above approach import java.util.*; class GFG{ // Function to count the elements with // sum of the first that many natural // numbers less than or equal to K static int Count( int N, int K) { // If K equals to 0 if (K == 0 ) return 0 ; // Stores the result int res = 0 ; int low = 1 , high = N; // Iterate until low is less than // or equal to high while (low <= high) { int mid = (low + high) / 2 ; // Stores the sum of first mid // natural numbers int sum = (mid * mid + mid) / 2 ; // If sum is less than or equal // to K if (sum <= K) { // Update res and low res = Math.max(res, mid); low = mid + 1 ; } // Otherwise, else { // Update high = mid - 1 ; } } // Return res return res; } // Driver Code public static void main(String[] args) { // Input int N = 6 , K = 14 ; // Function call System.out.println(Count(N, K)); } } // This code is contributed by hritikrommie. |
Python3
# Python3 program for the above approach # Function to count the elements with # sum of the first that many natural # numbers less than or equal to K def Count(N, K): # If K equals to 0 if (K = = 0 ): return 0 # Stores the result res = 0 low = 1 high = N # Iterate until low is less than # or equal to high while (low < = high): mid = (low + high) / / 2 # Stores the sum of first mid # natural numbers sum = (mid * mid + mid) / / 2 # If sum is less than or equal # to K if ( sum < = K): # Update res and low res = max (res, mid) low = mid + 1 # Otherwise, else : # Update high = mid - 1 # Return res return res # Driver Code if __name__ = = '__main__' : # Input N = 6 K = 14 # Function call print (Count(N, K)) # This code is contributed by shivanisinghss2110 |
C#
// C# program for above approach using System; class GFG{ // Function to count the elements with // sum of the first that many natural // numbers less than or equal to K static int Count( int N, int K) { // If K equals to 0 if (K == 0) return 0; // Stores the result int res = 0; int low = 1, high = N; // Iterate until low is less than // or equal to high while (low <= high) { int mid = (low + high) / 2; // Stores the sum of first mid // natural numbers int sum = (mid * mid + mid) / 2; // If sum is less than or equal // to K if (sum <= K) { // Update res and low res = Math.Max(res, mid); low = mid + 1; } // Otherwise, else { // Update high = mid - 1; } } // Return res return res; } // Driver Code public static void Main(String[] args) { // Input int N = 6, K = 14; // Function call Console.Write (Count(N, K)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript program for above approach // Function to count the elements with // sum of the first that many natural // numbers less than or equal to K function Count( N, K) { // If K equals to 0 if (K == 0) return 0; // Stores the result var res = 0; var low = 2, high = N; // Iterate until low is less than // or equal to high while (low <= high) { var mid = (low + high) / 2; // Stores the sum of first mid // natural numbers var sum = (mid * mid + mid) / 2; // If sum is less than or equal // to K if (sum <= K) { // Update res and low res = Math.max(res, mid); low = mid + 1; } // Otherwise, else { // Update high = mid - 1; } } // Return res return res; } // Driver Code // Input var N = 6, K = 14; // Function call document.write(Count(N, K)); // This code is contributed by shivanisinghss2110. </script> |
4
Time Complexity: O(log(N))
Auxiliary Space: O(1)
Contact Us