JavaScriptで「良い基数(Good Base)」の最小値を求めるアルゴリズム

良い基数(Good Base)とは

整数 num に対して、num を基数 k で表したときに、そのすべての桁が 1 になるような k(k >= 2)のことを「良い基数(Good Base)」と呼びます。

例えば、13 を基数 3 で表すと 111 となるため、3 は num = 13 における良い基数です。

問題の概要

数値を表す文字列 str を唯一の引数として受け取り、str の良い基数となる最小の数値を文字列形式で返す JavaScript 関数を作成する必要があります。

例えば、関数への入力が以下の場合:

const str = "4681";

出力は次のようになります。

const output = "8";

出力の説明

これは、4681 を基数 8 で表すと 11111 になるためです。

実装のポイント

この問題では、数値が非常に大きくなる可能性があるため、JavaScript の BigInt を使用して正確な演算を行います。また、桁数ごとに「すべての桁が 1 になる基数」が存在するかを 二分探索 で効率的に調べることで、計算量を抑えています。桁数が多いほど基数は小さくなるため、桁数の大きい方から順に探索することで、最初に見つかった基数が最小の良い基数となります。どの桁数でも見つからない場合は、num - 1(基数 10 で「11」と表される)が必ず答えになります。

コード例

この実装は以下のようになります。

const str = "4681";
const smallestGoodBase = (n = '1') => {
   const N = BigInt(n), bigint2 = BigInt(2), bigint1 = BigInt(1), bigint0 = BigInt(0)
   let maxLen = countLength(N, bigint2) // result at most maxLen 1s
   const findInHalf = (length, smaller = bigint2, bigger = N) => {
      if (smaller > bigger){
         return [false];
      };
      if (smaller == bigger) {
         return [valueOf1s(smaller, length) == N, smaller]
      };
      let mid = (smaller + bigger) / bigint2;
      let val = valueOf1s(mid, length);
      if(val == N){
         return [true, mid];
      };
      if (val > N){
         return findInHalf(length, smaller, mid - bigint1);
      };
      return findInHalf(length, mid + bigint1, bigger);
   };
   for (let length = maxLen; length > 0; length--) {
      let [found, base] = findInHalf(length);
      if(found){
         return '' + base;
      }
   };
   return '' + (N - 1);
   function valueOf1s(base, lengthOf1s) {
      let t = bigint1
      for (let i = 1; i < lengthOf1s; i++) {
         t *= base
         t += bigint1
      }
      return t
   }
   function countLength(N, base) {
      let t = N, len = 0
      while (t > bigint0) {
         t /= base
         len++
      }
      return len
   }
};
console.log(smallestGoodBase(str));

出力結果

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

8