Good Base
Với số nguyên num, gọi k (k ≥ 2) là good base nếu biểu diễn num ở cơ số k toàn chữ số 1. Ví dụ: 13 cơ số 3 là 111 -> 3 là good base của 13.
Vấn đề
Cần viết hàm JS nhận chuỗi str biểu diễn số, trả về chuỗi biểu diễn cơ số tốt nhỏ nhất.
Ví dụ:
const str = "4681";
Kết quả:
const output = "8";
Giải thích:
4681 cơ số 8 là 11111.
Ví dụ
Mã thực hiện:
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) // kết quả tối đa maxLen chữ số 1 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));
Kết quả
Kết quả in ra console:
8