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.