Please help to calculate the time complexity of the following code
Code
...
#include <bits/stdc++.h>
using namespace std;
#define tr ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define tst \
int t; \
cin >> t; \
while (t--)
typedef long long ll;
ll zeroCount(ll n)
{
ll cnt = 0;
if (n == 0)
return 0;
while (n % 10 == 0)
{
cnt++;
n /= 10;
}
return cnt;
}
ll cmp(ll n, ll k)
{
ll c1 = zeroCount(n), c2 = zeroCount(k);
if (c1 == c2)
{
return max(n, k);
}
else if (c1 > c2)
return n;
else
return k;
}
int main()
{
tr;
tst
{
ll n, m;
cin >> n >> m;
if (m <= 100)
{
ll an = 0;
for (int k = 1; k <= m; k++)
{
an = cmp(an, k * n);
}
cout << an << '\n';
continue;
}
vector<ll> digit;
ll tt = m;
while (tt)
{
digit.emplace_back(tt % 10);
tt /= 10;
}
reverse(digit.begin(), digit.end());
ll ans = 0;
ll i, j;
ll sz = digit.size();
ll tem = digit[0] * 100 + digit[1] * 10 + digit[2];
for (i = 100; i <= tem; i++)
{
ll tTem = i;
for (j = 3; j < sz; j++)
tTem *= 10;
ans = cmp(ans, tTem * n);
}
cout << ans << '\n';
}
}
Can this code pass in 1 second for large value of both n
and m
which can be in the rang of 1 - 1e9
The range of the test case is 10^4