FCTRL Time Limit Exceeded

general
, ,
1

#include
using namespace std;
int main()
{
int t;
cin>>t;
while (t–)
{
int n;
int five = 0;
cin>>n;
int i = 5;
for (; i <=n; i=i+5)
{
int k = 0, m = i;
while (m % 5 == 0)
{
m = m / 5;
k++;
}
five += k;
}
printf("%i\n", five);
}
return 0;
}

Time Limit Exceeded, I’ve tried using scanf instead of cin but that gives me a segmentaton error(SIGSEGV), what else can I change in the code here to optimise it?

2

You can compute that in O(log5(n)) which is less than O(30) in every case.

Let’s take x as 5 initially.

Let Y be (floor)N/x if Y is 0 break the loop else add to the result and Multiply x by 5 and repeat this step.

Example. N = 201.

Ans += 201/5 + 201/25 + 201/125 + 201/625 (Which is 0 so we stop here).

Ans = 40 + 8 + 1 = 49.

Here’s the code. [cpp]