Make a Power of Two
Contest: Codeforces Round 739 (Div. 3)
Difficulty rating: 1300
Tags: greedy, math, strings

You are given an integer $$$n$$$. In $$$1$$$ move, you can do one of the following actions:

- erase any digit of the number (it's acceptable that the number before the operation has exactly one digit and after the operation, it is "empty");
- add one digit to the right.

The actions may be performed in any order any number of times.

Note that if, after deleting some digit from a number, it will contain leading zeroes, they will not be deleted. E.g. if you delete from the number $$$301$$$ the digit $$$3$$$, the result is the number $$$01$$$ (not $$$1$$$).

You need to perform the minimum number of actions to make the number any power of $$$2$$$ (i.e. there's an integer $$$k$$$ ($$$k \ge 0$$$) such that the resulting number is equal to $$$2^k$$$). The resulting number must not have leading zeroes.

E.g. consider $$$n=1052$$$. The answer is equal to $$$2$$$. First, let's add to the right one digit $$$4$$$ (the result will be $$$10524$$$). Then let's erase the digit $$$5$$$, so the result will be $$$1024$$$ which is a power of $$$2$$$.

E.g. consider $$$n=8888$$$. The answer is equal to $$$3$$$. Let's erase any of the digits $$$8$$$ three times. The result will be $$$8$$$ which is a power of $$$2$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of one line containing one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output format:
For each test case, output in a separate line one integer $$$m$$$ — the minimum number of moves to transform the number into any power of $$$2$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The answer for the first test case was considered above.

The answer for the second test case was considered above.

In the third test case, it's enough to add to the right the digit $$$4$$$ — the number $$$6$$$ will turn into $$$64$$$.

In the fourth test case, let's add to the right the digit $$$8$$$ and then erase $$$7$$$ and $$$5$$$ — the taken number will turn into $$$8$$$.

The numbers of the fifth and the sixth test cases are already powers of two so there's no need to make any move.

In the seventh test case, you can delete first of all the digit $$$3$$$ (the result is $$$01$$$) and then the digit $$$0$$$ (the result is $$$1$$$).

Example input:
12
1052
8888
6
75
128
1
301
12048
1504
6656
1000000000
687194767

Example output:
2
3
1
3
0
0
2
1
3
4
9
2

Editorial:
Suppose we must turn $$$n$$$ into some specific number $$$x$$$. In this case, we can use the following greedy algorithm. Consider the string forms — $$$s_n$$$ and $$$s_x$$$ — of the numbers $$$n$$$ and $$$x$$$, respectively. Let's make a pointer $$$p_n$$$ pointing at the first character of the string $$$s_n$$$ and a pointer $$$p_x$$$ pointing at the first character of the string $$$s_x$$$. Let's initialize a variable $$$taken = 0$$$ in which we will store a number of selected characters. Until any of the pointers points at the place that is out of the corresponding string, let's do the following procedure: if the characters to which the pointers point are equal, we will take the character (increase $$$taken$$$ by $$$1$$$) and move both pointers $$$1$$$ character to the right, otherwise, the only action we must perform is to move $$$s_n$$$ $$$1$$$ character to the right. The variable $$$taken$$$ will contain after the whole process the length of the longest subsequence of $$$s_n$$$ equal to a prefix of $$$s_x$$$, i. e. the maximum number of original characters of $$$s_n$$$ that we will not erase. We must add to the resulting string all remaining characters of $$$s_x$$$ to turn it into $$$s_x$$$. Therefore, we must erase $$$|s_n| - taken$$$ digits and add $$$|s_x| - taken$$$ digits so the answer for this subproblem is $$$ans(n, x) = |s_n| + |s_x| - 2 \cdot taken$$$ where $$$|s|$$$ means the length of a string $$$s$$$.
Suppose we have a set $$$X$$$ of powers of two such that it's enough to consider to get the problem's answer. The problem can be solved as follows: for each $$$x \in X$$$ let's calculate the answer for the subproblem described above and select the value of $$$\min\limits_{x \in X} ans(n,x)$$$ as the answer.
What set of powers of two we can take? Suppose the number $$$n$$$ consists of no more than $$$9$$$ digits. The answer for each $$$n$$$ consisting of $$$d$$$ digits doesn't exceed $$$d + 1$$$, hence we can get this value by turning the number into $$$1$$$ in $$$d + 1$$$ move adding $$$1$$$ to the right of the number, and erasing all other $$$d$$$ digits. Suppose there's a number $$$x$$$ such that $$$ans(n, x) \le d$$$. So it consists of no more than $$$2 \cdot d$$$ digits — this value can be reached as follows: we must not erase any digit and add $$$d$$$ digits. Therefore, if $$$d \le 9$$$, each number $$$x$$$ such that $$$ans(n, x) \le d$$$ consists of no more than $$$18$$$ digits, hence $$$x < 10^{18}$$$.
Suppose $$$n$$$ consists of more than $$$9$$$ digits. Then $$$n = 10^9$$$ because $$$n \le 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) \le 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}$$$.