OEIS A036301 is a sequence of numbers $ n $ such that the sum of the even digits of $ n $ equals the sum of the odd digits of $ n $. Let's call these numbers "balanced". Given an input positive integer $ k $, I would like a procedure that finds the nearest balanced integer. Occasionally, $ k $ might be equidistant from two balanced integers, in which case the procedure should output both. For a relatively small $ k $, this problem is not too difficult to brute-force. But for a large $ k $, if there is a great disparity between the sum of the even digits and the sum of the odd digits, brute force takes too long.
For example, if $ k = 1037708753757778746280242 $, the nearest balanced integer appears to be $ 1037708753757778800288888 $. How do we quickly determine this without checking all integers from $ k - 54008646 $ to $ k + 54008646 $?