Given $$$N \leq 10^{9}$$$, I want to place a vertical bar between any two consecutive digits to form two new integers. Let's call them $$$X$$$ and $$$Y$$$. How can we minimize $$$|X - Y|$$$?
Clearly, $$$N$$$ is so large, so we must get some non-linear solution. I thought about implementing something in which we first and second part, and we manually remove and add one digit at a time. However, this seems to be a little bit difficult when there are zeros.
For example, consider $$$30001$$$. We can split at the first zero to get $$$3$$$ and $$$0001$$$, so the answer is $$$|3 - 1| = 2$$$.
I also thought about using DP, but I think even a linear solution would get TLE. Any ideas are greatly appreciated.
These constraints mean that N is at most 9 digits, so there are at most 9 places to cut the integer and just bashing each possibility works. Also, removing and adding one digit at a time works too, for example to transition from 3000 to 30001 you'd multiply by 10 and add the next digit, and to transition from 0001 to 001 you'd subtract the thousands digit.