JavaScriptで最も近いギャップフル数を求めるアルゴリズム

「ギャップフル数（gapful number）」とは、3桁以上の整数のうち、「先頭の数字」と「末尾の数字」をつなげてできる2桁の数で割り切れる数のことです。この条件を満たす最小の数は 100 です。100 の場合、先頭が「1」、末尾が「0」なので、これらをつなげると「10」になり、100 は 10 で割り切れます。したがって、100 はギャップフル数であるといえます。

今回の課題は、ある数 n を受け取り、n に最も近いギャップフル数（n 自身を含む）を返す関数を作成することです。ただし、距離が等しいギャップフル数が 2 つ見つかった場合は、小さい方の数を返すものとします。

いくつか例を挙げます。

gapful(25) ➞ 100

gapful(100) ➞ 100

gapful(103) ➞ 105

アプローチ

まず、渡された数がギャップフル数かどうかを判定する関数 isGapful を用意します。判定は次の手順で行います。

• 数が 100 未満（3桁未満）の場合は false を返す
• 数値を文字列化し、先頭の文字と末尾の文字を取り出して連結する
• 連結してできた 2 桁の数で元の数が割り切れれば true、そうでなければ false を返す

次に、n を基準として上方向と下方向の両方へ順に探索し、それぞれ最初に見つかったギャップフル数までの距離を比較します。より近い方を返し、距離が同じ場合は小さい方（下方向の結果）を返します。なお、n が 100 未満の場合は下方向にギャップフル数が存在しないため、上方向の探索結果をそのまま返せば十分です。

コード例

const num = 4780;

// ギャップフル数かどうかを判定する関数
const isGapful = n => {
   if (n < 100){
      return false;
   }
   const str = String(n);
   const edges = Number(str[0] + str[str.length - 1]);
   return n % edges === 0;
}

// 最も近いギャップフル数を返す関数
function getClosestGapful(n) {
   let left = n, right = n;
   // 上方向へ探索
   while (!isGapful(right)){
      right++;
   }
   // 3桁未満なら上方向の結果がそのまま答えになる
   if (n < 100){
      return right;
   }
   // 下方向へ探索
   while (!isGapful(left)){
      left--;
   }
   // 距離が近い方を返す（同距離の場合は小さい方）
   return n - left <= right - n ? left : right;
};
console.log(getClosestGapful(25));
console.log(getClosestGapful(num));

出力結果

コンソールには次のように出力されます。

100
4760

処理の流れの解説

getClosestGapful(25) の場合、25 は 3 桁未満なのでギャップフル数になり得ません。そこで上方向へ探索を続けると、条件を満たす最小のギャップフル数である 100 が返されます。

一方、getClosestGapful(4780) の場合を見てみましょう。下方向へ探索すると 4760（4780 − 4760 = 20）、上方向へ探索すると 4800（4800 − 4780 = 20）が見つかります。どちらも 4780 からの距離が 20 で等しいため、ルールに従って小さい方の 4760 が返されるという仕組みです。このように、判定関数と双方向の線形探索を組み合わせることで、任意の数に対して最も近いギャップフル数をシンプルに求めることができます。