C++で数値がジャンブル数かどうかを判定する方法

本記事では、ある整数が「ジャンブル数（jumbled number）」と呼ばれる条件を満たしているかどうかを判定する、興味深い問題をC++で解いていきます。

ジャンブル数とは？

ジャンブル数とは、すべての隣り合う桁同士の差が最大でも1であるような数のことです。例えば「1223」は隣接する桁の差がそれぞれ1以下であるためジャンブル数ですが、「1256」は2と5の差が3あるためジャンブル数にはなりません。

判定アルゴリズム

この問題を解くには、数値の下の桁から順に隣接する桁との差を調べ、差が1より大きい桁がひとつでも見つかった時点でfalseを返し、最後まで確認できればtrueを返すという手順を踏みます。具体的には以下の流れになります。

1. 数値を10で割った余りから、現在注目している最下位の桁を取得します。
2. 数値を10で割った商に対して再度10の剰余を取ることで、その隣の桁を取得します。
3. 両者の差の絶対値が1より大きければ、ジャンブル数ではないのでfalseを返します。
4. すべての桁の確認が終わったらtrueを返します。

なお、1桁の数には隣接する桁が存在しないため、常にジャンブル数として扱います。

C++での実装例

#include <iostream>
#include <cmath>
using namespace std;

bool isJumbled(int number) {
    if (number / 10 == 0) // 1桁の数は常にジャンブル数
        return true;
    while (number != 0) {
        if (number / 10 == 0) // すべての桁を確認し終えたらtrueを返す
            return true;
        int curr_digit = number % 10;
        int prev_digit = (number / 10) % 10;
        if (abs(prev_digit - curr_digit) > 1)
            return false;
        number = number / 10;
    }
    return true;
}

int main() {
    int n = 1223;
    if (isJumbled(n)) {
        cout << n << " is Jumbled";
    } else {
        cout << n << " is not Jumbled";
    }
}

実行結果

1223 is Jumbled

処理の流れのポイント

入力が1223の場合、下の桁から順に「3と2」「2と2」「2と1」の差を確認していきます。いずれも差は1以下なので、この数はジャンブル数であると判定されます。一方、1256のような数では「5と2」の差が3となった時点で即座にfalseが返されるため、無駄なく効率的に判定できます。計算量は桁数に比例するO(log n)であり、非常にシンプルながら実用的なアルゴリズムです。