Problem statement

https://binarysearch.com/problems/Next-Closest-Odd-Digit-Number/

Solution

Use math and greedy strategy. Find smaller and bigger closest numbers.

  1. Find biggest prefix fully with odd digits. If we have something like xxxx0... or xxxx, where xxxx are digit numbers, then we need to find the biggest suffix of this prefix with 1, like 135111 goes to 133999 and 1111 goes to 999. If it is xxxxy wher y >= 1, just have xxxx(y-1)9..9.
  2. For closest bigger number it is a bit easier: have just xxxx(y+1)1..1.

Complexity

It is O(m) for time and space, where m is number of digits in n.

Code

class Solution:
    def solve(self, n):
        s = str(n)
        m = len(s)
        i = 0
        while int(s[i]) % 2 == 1:
            i += 1

        if i == len(s) or s[i] == "0":
            j = i - 1
            while j > 0 and s[j-1] == "1": j -= 1
            p0 = "9"*(m-1) if j == 0 else s[:j-1] + str(int(s[j-1])-2) + "9" * (m-j)
        else:
            p0 = s[:i] + str(int(s[i])-1) + "9" * (m-i-1)

        p1 = s[:i] + str(int(s[i])+1) + "1" * (m-i-1)

        c0, c1 = int(p0), int(p1)
        if n - c0 < c1 - n:
            return c0
        else:
            return c1