Cơ sở tốt
Đối với một số nguyên num, chúng ta gọi k (k> =2) là một cơ sở tốt của num, nếu tất cả các chữ số của num cơ số k là 1.
Ví dụ:13 cơ số 3 là 111, do đó 3 là cơ sở tốt cho num =13
Vấn đề
Chúng tôi được yêu cầu viết một hàm JavaScript lấy chuỗi str đại diện cho một số làm đối số duy nhất. Hàm sẽ trả về biểu diễn chuỗi của số nhỏ nhất, đây là cơ sở tốt cho str.
Ví dụ:nếu đầu vào của hàm là -
const str = "4681";
Sau đó, đầu ra phải là -
const output = "8";
Giải thích đầu ra:
Vì 4681 cơ số 8 là 11111
Ví dụ
Mã cho điều này sẽ là -
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)); Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
8