*Author*: Dikshita Majumdar

*Testers*: Sameer , Keshav Goyal

*Editorialist*: Dikshita Majumdar

# DIFFICULTY:

CAKEWALK

# PREREQUISITES

Basic Maths.

# PROBLEM:

You are given an integer **n** , and you have to find the smallest integer **m** such that the sum of first **m** **odd numbers** is **greater than or equal** to the **sum of first n natural numbers** .

# EXPLANATION:

The sum of first m odd numbers is m^{2} and the sum of first n natural numbers is n*(n+1)/2.

So the mathematical equation comes down to:

m^{2} \geq n*(n+1)/2

m \geq \sqrt{n*(n+1)/2}

So the value of m will be \lceil \sqrt{n*(n+1)/2} \rceil

# TIME COMPLEXITY:

The time complexity for the problem is: O(1)

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
// your code goes here
ll t;
cin>>t;
assert(t >= 1 and t <= 1e5);
while(t--){
ll n; cin>>n;
assert(n >= 1 and n <= 1e9);
ll sum=(n*(n+1))/2;
ll sq=sqrt(sum);
if (sq*sq<sum) sq++;
cout<<sq<<endl;
}
return 0;
}
```

## Tester's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
// your code goes here
ll t;
cin>>t;
assert(t >= 1 and t <= 100000);
while(t--){
ll n; cin>>n;
assert(n >= 1 and n <= 1000000000);
ll d = n * (n + 1) / 2;
ll ans = ceil((double)sqrt(d));
cout<<ans<<endl;
}
return 0;
}
```

```
Any other solution or feedback can be posted in the comments. We are always open for them.
```