[1] Carries in addition and the digit sum

Generally, the sum of digits in \(a+b\), \(f(a+b)\), satisfies the following:

\(f(a+b) = f(a) + f(b) - 9k\), where \(k\) is the number of carries when calculating \(a+b\) using the column method.

This is because a carry subtracts \(10\) from a digit and adds \(1\) to the next digit.

---

[2] Finding \(M\)

Assume that a positive integer \(x\) satisfies \(f(x)=N\). From [1], we have \(f(2x)=f(x) + f(x) - 9k = 2N - 9k\), where \(k\) is the number of carries when calculating \(x+x\) using the column method.

Thus, the following can be deduced:

• \(f(2x) \leq 2N\) always holds;
• \(f(2x) = 2N\) holds if and only if all digits in \(x\) are at most \(4\).

There does exist an \(x\) such that \(f(x)=N\) and all digits in \(x\) are at most \(4\) (for instance, \(x = \underbrace{111\cdots 111}_{N}\)), so we find that \(M = 2N\).

---

[3] Finding \(x\)

Now let us find the smallest positive integer \(x\) such that \(f(x)=N\) and \(f(2x) = 2N\).

Such \(x\) satisfies the following:

• All digits are at most \(4\);
• All but the most significant digit are \(4\).

The first condition is already discussed in [2].

Let us verify the second condition. Assume that \(x\) has a non-most-significant digit that is at most \(3\). Look at the most significant such digit. By increasing that digit by \(1\) and decreasing the next significant digit by \(1\), we can decrease \(x\) while still satisfying \(f(x)=N\) and \(f(2x)=2N\), which contradicts the minimality of \(x\).

There is only one \(x\) such that \(f(x) = N\) and those two conditions are satisfied, which is:

• \(x = \underbrace{44\cdots 44}_{k}\) if \(N = 4k\);
• \(x = 1\underbrace{44\cdots 44}_{k}\) if \(N = 4k+1\);
• \(x = 2\underbrace{44\cdots 44}_{k}\) if \(N = 4k+2\);
• \(x = 3\underbrace{44\cdots 44}_{k}\) if \(N = 4k+3\).

These \(M\) and \(x\) should be printed. Output takes \(\Theta(N)\) time, for a time complexity of \(\Theta(N)\).