Please help to calculate the time complexity of the following code ↵
↵
<spoiler summary="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';↵
}↵
} ↵
~~~~~↵
↵
↵
</spoiler>↵
↵
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``
↵
<spoiler summary="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';↵
}↵
} ↵
~~~~~↵
↵
↵
</spoiler>↵
↵
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``
