Pythonで数値が8進数表記の回文かどうかを判定する方法

ある数値が与えられたとき、それが8進数として表現されているのか、それとも10進数なのかを判別し、8進数表記において回文（前から読んでも後ろから読んでも同じ並び）になっているかどうかを判定する問題を考えてみましょう。

具体的には、次のようなルールで処理を行います。

• 数値のいずれかの桁に「8」や「9」が含まれている場合 → その数値は10進数と判断し、8進数に変換してから回文判定を行う
• すべての桁が「0〜7」の範囲に収まっている場合 → その数値は8進数としてそのまま扱い、各桁を取り出して回文判定を行う

たとえば、入力が num = 178 の場合を考えてみます。「8」という数字は8進数では使用できないため、この数値は10進数形式だと判断されます。178を8進数に変換すると 262 となり、これは回文なので出力は True になります。

解き方の手順

1. 基数の決定： num のすべての桁が8未満であれば、その数値は8進数として扱うため基数を10に設定し（桁をそのまま取り出す）、8以上の桁が含まれていれば10進数と判断して基数を8に設定します。
2. 各桁の抽出： 空のリスト oct_list を用意し、num が0になるまで次の処理を繰り返します。
   • oct_list の末尾に「num を base で割った余り」を追加する
   • num を「num を base で割った商」で更新する
3. 回文判定： 先頭を指すポインタ k と末尾を指すポインタ j を用意し、k ≤ j の間、oct_list[j] と oct_list[k] を比較します。一致しないペアが見つかった時点で False を返し、最後まで一致すれば True を返します。

実装例

以下にPythonでの実装例を示します。

def is_all_under_8(num):
    while num:
        if (num % 10) >= 8:
            return False
        else:
            num = int(num / 10)
    return True


def solve(num):
    # 8以上の桁を含む場合は10進数とみなし、8進数へ変換するため基数8を使用
    base = 8 if not is_all_under_8(num) else 10
    oct_list = []
    while num != 0:
        oct_list.append(num % base)
        num = int(num / base)

    # 回文判定（両端から中央に向かって比較）
    j = len(oct_list) - 1
    k = 0
    while k <= j:
        if oct_list[j] != oct_list[k]:
            return False
        j -= 1
        k += 1
    return True


num = 178
print(solve(num))

入力

178

出力

True

処理の流れを確認

num = 178 の場合、桁に「8」が含まれているため is_all_under_8() は False を返し、基数は8に設定されます。その後の除算処理では、次のように各桁が抽出されていきます。

• 178 ÷ 8 = 22 余り 2
• 22 ÷ 8 = 2 余り 6
• 2 ÷ 8 = 0 余り 2

結果として oct_list = [2, 6, 2] となり、両端の要素が一致しているため回文と判定され、True が出力されます。

計算量について

桁の抽出と回文判定は、いずれも数値の桁数に比例した処理となるため、全体の時間計算量は O(log n) です。また、桁を格納するリストが必要となるため、必要な追加メモリも O(log n) となります（n は入力された数値）。