How come this approach works even though it performs more than 10^9 operations? https://www.codechef.com/viewsolution/25391464
P is incremented by 1 each time.
So for a input :
1
1000000000
It performs more than 10^9 operations.
For time limit 1sec we are supposed to keep a upper bound of 10^8 operations, or not?
Look at the lines 27 to 32
while(p<=cur)
{
ans++;
y+=p*p;
while(p*p<=y) {p++;}
}
at line 31, we are incrementing the value P by 1 each time in the while loop,
not squaring it
yes, so imagine how would the condition look like. I’ll explain with an example.
let xf=100
at p=1 (11<100)
at p=2 (22<100)
.
.
.
at p=6 (66<100)
at p=7 (77<100)
at p=10 (10*10<100)
at this increases fast so for xf=100 it took just 10 i.e √n iteration