// This function is working in O(max(s1.length(), s2.length())
int recur(string s1, string s2, int x, int y)
{
if (x >= s1.length() || y >= s2.length())
return 0;
int t1 = 0, t2 = 0;
if (s1[x] == s2[y])
t1 = 1 + recur(s1, s2, x + 1, y + 1);
else
t2 = recur(s1, s2, x, y + 1);
return max(t1, t2);
}
// storing the power to 2 from 0-40
vector<string> make_power_of_2()
{
vector<string> vs;
vs.pb("1");
int ans = 1;
for (int i = 1; i <= 40; i++)
{
ans = ans * 2;
vs.pb(to_string(ans));
}
return vs;
}
void solve()
{
vector<string> vs = make_power_of_2();
int n;
cin >> n;
string str = to_string(n);
int ans = INT_MAX;
int flag = 0;
for (int i = 0; i < vs.size(); i++)
{
int z = recur(vs[i], str, 0, 0);
ans = min(ans, (vs[i].length() + str.length() - 2 * z));
}
cout << min(ans, (int)(str.length() + 1)) << endl;
}
make_power_of_2() should be preprocessed. You're calling it per testcase without clearing it (looking at Your submission). 40 push_backs per case making its size 40 * 10 ^ 4.
Call it once, or clear the vs vector after each testcase.
use 2**62 or larger
No reason for using it as it is cleary mentioned in the question that the value of n<=10⁹ , so even if we add a digit to the right of n it cannot exceed 2^36
u would get a wa generating all powers till 36. you have to generate atleast till 56 because 2^56 > 1e18
And why is it , that we've to generate till 1e18 , the upper limit in the question is 1e9 and the max number of moves to get a power of 2 is (number of digits+1) , that gives us 1e10 in worst scenario
From the editorial of this round:
Suppose n consists of more than 9 digits. Then n=10^9 because n≤10^9 according to the input format. The answer for the number doesn't exceed 9 — we can get this answer if we erase all 0 from the number to turn it into 1. Suppose there's a number x such that ans(n,x)≤8. This number can consist of no more than 18 digits (10 digits of n plus 8 digits), hence x<10^18.
Therefore, it's enough to consider all powers of two that are less than 10^18
Gotcha ;)