ฐานที่ดี
สำหรับจำนวนเต็ม เราเรียก k (k>=2) เป็นฐานที่ดีของ num ถ้าตัวเลขทั้งหมดของ num ฐาน k เป็น 1
ตัวอย่างเช่น:13 ฐาน 3 คือ 111 ดังนั้น 3 จึงเป็นฐานที่ดีสำหรับ num =13
ปัญหา
เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับสตริง str ที่แสดงตัวเลขเป็นอาร์กิวเมนต์เดียว ฟังก์ชันควรส่งคืนการแสดงสตริงของจำนวนที่น้อยที่สุดที่เป็นไปได้ซึ่งเป็นฐานที่ดีสำหรับ str
ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −
const str = "4681";
จากนั้นผลลัพธ์ควรเป็น −
const output = "8";
คำอธิบายผลลัพธ์:
เพราะ 4681 ฐาน 8 คือ 11111
ตัวอย่าง
รหัสสำหรับสิ่งนี้จะเป็น −
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
