জাভাস্ক্রিপ্টে সবচেয়ে ছোট ভাল বেস খোঁজা

ভাল ভিত্তি

একটি পূর্ণসংখ্যার জন্য, আমরা k (k>=2) কে num-এর একটি ভাল ভিত্তি বলি, যদি num base k-এর সমস্ত সংখ্যা 1 হয়।

উদাহরণস্বরূপ:13 বেস 3 হল 111, তাই 3 হল num =13 এর জন্য একটি ভাল বেস

সমস্যা

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা স্ট্রিং স্ট্র-এ লাগে যা একটি সংখ্যাকে একমাত্র যুক্তি হিসাবে উপস্থাপন করে। ফাংশনটি সবচেয়ে ছোট সম্ভাব্য সংখ্যার স্ট্রিং উপস্থাপনা প্রদান করবে যা স্ট্রের জন্য একটি ভাল ভিত্তি।

উদাহরণস্বরূপ, যদি ফাংশনে ইনপুট হয় −

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