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

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++

#include <bits/stdc++.h> using namespace std;    void minimumNumber(int K, int X) {          if (K > X) {         cout << "-1";         return;     }             int ans = 0;                  int sum = 0;             for (int i = K; i <= X; i++) {            sum += i;                              if (sum >= X) {             ans = i;             break;         }     }             cout << ans; }    int main() {     int K = 5, X = 13;     minimumNumber(K, X);        return 0; }

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++

#include <bits/stdc++.h> using namespace std;    bool isGreaterEqual(int N, int K, int X) {     return ((N * 1LL * (N + 1) / 2)             - ((K - 1) * 1LL * K / 2))            >= X; }    void minimumNumber(int K, int X) {          if (K > X) {         cout << "-1";         return;     }        int low = K, high = X, res = -1;             while (low <= high) {         int mid = low + (high - low) / 2;                              if (isGreaterEqual(mid, K, X)) {                             res = mid;                             high = mid - 1;         }                     else             low = mid + 1;     }                  cout << res; }    int main() {     int K = 5, X = 13;     minimumNumber(K, X);        return 0; }

Time Complexity: O(log(X – K))
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets