 # REC25A - Editorial

contest

Author: Dikshita Majumdar
Testers: Sameer , Keshav Goyal
Editorialist: Dikshita Majumdar

CAKEWALK

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() {
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() {
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.