গুড বেস
একটি ইন্টিজার num-এর জন্য, k (k >= 2) একটি গুড বেস যদি num-কে বেস k-এ রিপ্রেজেন্ট করলে সব ডিজিট ১ হয়।
উদাহরণ: ১৩ বেস ৩-এ ১১১, তাই ৩ হলো ১৩-এর একটি গুড বেস।
সমস্যা
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি স্ট্রিং str (যেটি একটি সংখ্যা রিপ্রেজেন্ট করে) একমাত্র আর্গুমেন্ট হিসেবে নেবে। ফাংশনটি স্ট্রিং রিপ্রেজেন্টেশন রিটার্ন করবে যেটি str-এর জন্য সবচেয়ে ছোট সম্ভব গুড বেস।
উদাহরণ:
const str = "4681";
আউটপুট হবে:
const output = "8";
আউটপুট ব্যাখ্যা:
কারণ ৪৬৮১ বেস ৮-এ ১১১১১।
উদাহরণ
কোডটি নিচের মতো (BigInt ও বাইনারি সার্চ):
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
