Pythonで全桁が奇数となるnに最も近い数を見つけるプログラム

問題の概要

ある数値 n が与えられたとき、「すべての桁が奇数である数」の中から n に最も近い値を見つけることを考えます。もし n からの距離が同じ候補が 2 つ存在する場合には、大きい方の値を返します。

例えば、入力が n = 243 の場合、出力は 199 となります。243 より大きい側で最も近い全桁奇数の数は 311、小さい側は 199 であり、差はそれぞれ 68 と 44。したがって、より近い 199 が答えになります。

解法の考え方

この問題は、次の手順で解くことができます。

• まず first_even := -1 と初期化します。
• s := n を文字列化したもの、l := s の長さ とします。
• i を 0 から l まで走査し、s[i] が偶数であれば first_even := i としてループを抜けます。
• first_even が -1 のまま(偶数の桁が 1 つもない)であれば、そのまま n を返します。
• 「大きい側」の候補 big は、先頭から i 文字目までの部分文字列を数値化して 1 を加えた値とします。これにより、偶数だった桁が奇数へと繰り上がります。
• s[i] が "0" の場合は特別な処理が必要です。
  • s[i - 1] が "1" の場合:small は先頭から i 文字目までの数値から 1 を引いた値。
  • それ以外の場合:small は s[i : i + 1] の数値から 11 を引いた値。
• s[i] が "0" 以外の場合は、small は先頭から i 文字目までの数値から 1 を引いた値とします。
• 続いて i + 1 から l までの各位置について、big の末尾には "1" を、small の末尾には "9" を順に連結します。これにより、残りの桁を最小の奇数(1)または最大の奇数(9)で埋めた 2 つの候補が完成します。
• big と small を整数に変換し、d2 := big - n、d1 := n - small を計算します。
• d1 < d2 であれば small を返し、d1 >= d2 であれば big を返します(同点の場合は大きい方が採用されます)。

このアプローチのポイントは、左から最初に現れた偶数の桁だけを操作すればよいという点です。その桁を基準に「少し大きい側」と「少し小さい側」の 2 つの候補を作り、残りの桁を 1 と 9 で埋めることで、n との距離を簡単に比較できます。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

コード

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
        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))

入力

243

出力

199

まとめ

このアルゴリズムは、数値を文字列として扱い、最初に現れた偶数の桁を起点に上下 2 つの候補を生成することで、効率的に答えを求めます。桁数を k とすると計算量は O(k) に抑えられるため、非常に大きな数値でも高速に動作します。偶数の桁が 1 つも含まれていない場合は、その数自体が条件を満たしているため、変更なしでそのまま返されます。