Chương trình tìm số gần nhất có toàn chữ số lẻ bằng Python

Cho một số nguyên n, tìm số gần nhất với n sao cho mọi chữ số của nó đều là số lẻ. Nếu có hai số cách đều nhau, trả về số lớn hơn.

Ví dụ: n = 243 → kết quả là 199.

Giải thuật

• Tìm vị trí chữ số chẵn đầu tiên từ trái sang phải (first_even).
• Nếu không có chữ số chẵn, trả về n.
• Xây dựng hai ứng viên:
  • big: tăng phần tiền tố đến vị trí chẵn lên 1, phần còn lại điền toàn số 1.
  • small: giảm phần tiền tố xuống 1 (xử lý đặc biệt khi chữ số là 0), phần còn lại điền toàn số 9.
• So sánh khoảng cách từ n đến big và small, trả về số gần hơn (nếu bằng nhau lấy big).

Ví dụ minh họa

class Solution:
    def solve(self, n):
        first_even = -1
        s = str(n)
        l = len(s)
        for i in range(l):
            if int(s[i]) % 2 == 0:
                first_even = i
                break
        if first_even == -1:
            return n
        i = first_even
        big = str(int(s[:i+1]) + 1)
        if s[i] == "0":
            if s[i-1] == "1":
                small = str(int(s[:i+1]) - 1)
            else:
                small = str(int(s[i:i+1]) - 11)
        else:
            small = str(int(s[:i+1]) - 1)
        for i in range(i+1, l):
            big += "1"
            small += "9"
        big, small = int(big), int(small)
        d2 = big - n
        d1 = n - small
        if d1 < d2:
            return small
        elif d1 >= d2:
            return big

ob = Solution()
n = 243
print(ob.solve(n))

Đầu vào

243

Đầu ra

199