หา Good Base ที่เล็กที่สุดของตัวเลขใน JavaScript

Good Base

ฐาน k (k≥2) เรียกว่า Good Base ของ num หากเขียน num ในฐาน k แล้วตัวเลขทุกหลักเป็น 1

เช่น 13 ฐาน 3 = 111 → 3 เป็น Good Base ของ 13

ปัญหา

รับสตริง str แทนตัวเลข หา Good Base ที่เล็กที่สุด คืนเป็นสตริง

ตัวอย่าง

const str = "4681";

4681 ฐาน 8 = 11111 → ผลลัพธ์ "8"

โค้ดตัวอย่าง (BigInt + Binary Search)

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