Find the smallest value of N such that sum of first N natural numbers is ≥ NUM

Find the minimum number ‘N’ such that the sum of ‘N’ natural numbers is greater than or equal to a given number ‘NUM’ using Binary Search.

In this problem, we need to find the minimum number ‘N’ such that the sum of the first ‘N’ number is greater than or equal to the user given number ‘NUM’.
The Naive approach to solve this problem is to traverse from 1 to NUM and look for the number which is greater than or equal to NUM but it will take O(n) time here we are going to do it in O(log(N)) time.

Examples:

Input: NUM = 10
Output: N = 4
Explanation : 1+2+3+4=10

Input: NUM = 20
Output: N = 6
Explanation: 1+2+3+4+5+6= 21
21 > 20.

Formula used :

((n)*(n+1))/2 = sum of fisrt n natural numbers.

We basically ignore half of the elements just after one comparison and follow the following steps.

set the range within which the answer is surely present.
that is set the lower limit to 1 and upper limit to NUM.
take the middle element of the range and name it mid
if the sum of the first ‘mid’ natural numbers is equal to NUM then return mid.
if the sum of the first ‘mid’ natural numbers is greater but the sum of the first ‘mid-1’ natural numbers are smaller then return mid.
if the above cases fail and the sum of ‘mid ‘ natural numbers is greater than NUM go to the left half
if the above cases fail and the sum of ‘mid’ natural numbers is smaller than NUM then go to the right half.
repeat till you get the answer.

Implementation in C++:

#include <iostream>
using namespace std;
int minSUM(int NUM)
{
  int low = 1; 
  int high = NUM;
  // our answer lies between 1 to NUM
  // so we set low to 1 and high to NUM.
  for(;low<=high;)
  {
      int mid = (low+high)/2;
      // mid takes the middle element within our given range.
      int sum1 = (mid)*(mid+1)/2;
      // sum1 is the sum of first 'mid' natural numbers.
      int sum2 = (mid-1)*(mid)/2;
      // sum2 is the sum of first 'mid-1' natural numbers.
      if(NUM==sum1)
      {
           return mid;// if NUM==sum1 we return mid.
      }
      else if( NUM < sum1 and NUM > sum2)
      {
           return mid;
           // if sum1 is greater while sum2 is smaller than NUM
           /// that means mid is the correct answer and we return it.
      }
      else if ( NUM < sum1)
      {
           high = (mid-1);
           // if the above cases fail &amp; NUM &lt; sum1
           // that means answer is in the left half
      }
      else
      {
           low = (mid+1);
           // clearly now as NUM is greater than sum1
           // answer lies in right half
      }
  }
}
int main() {
    int NUM = 20 ;
    cout<<"N = "<<minSUM( NUM )<<endl;
    return 0;
}

Output:

N = 6

Time Complexity and auxiliary space analysis:

The time complexity of the above algorithm is clearly O(Log(n)).
The auxiliary space complexity is of O(1).