मान लीजिए हमारे पास एक पूर्णांक n है, हम k >= 2 को n का एक अच्छा आधार कहते हैं, जब n के आधार k में सभी अंक 1 होते हैं। इसलिए यदि संख्या n स्ट्रिंग के रूप में दी गई है, तो हमें n के सबसे छोटे अच्छे आधार को स्ट्रिंग के रूप में लौटाना होगा। इसलिए यदि संख्या 121 है, तो उत्तर 3 होगा, क्योंकि 121 आधार 3 में 11111 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- getSum() नामक एक विधि परिभाषित करें, यह x और length लेगा
- mainSum := 0 और temp := 1 सेट करें
- i के लिए range 0 से length - 1 तक −
- mainSum := mainSum + temp, temp := temp * x
- mainSum लौटाएं
- check() नामक एक विधि परिभाषित करें, यह n और length लेगा −
- low := 1, high := n
- जब तक high >= low −
- mid := low + (high - low) / 2
- mainSum := getSum(mid, length)
- यदि mainSum = n, तो mid लौटाएं
- अन्यथा जब mainSum > n, तो high := mid - 1
- अन्यथा low := mid + 1
- -1 लौटाएं
- मुख्य विधि से निम्नलिखित करें −
- n := दी गई संख्या
- i के लिए range 64 से 0 तक
- x := check(n, i)
- यदि x >= 2, तो x को स्ट्रिंग के रूप में लौटाएं
- n - 1 को स्ट्रिंग के रूप में लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
class Solution(object): def getSum(self, x, length): mainSum = 0 temp = 1 for i in range(length): mainSum += temp temp *= x return mainSum def check(self, n, length): low = 1 high = n while high >= low: mid = low + (high - low) // 2 mainSum = self.getSum(mid, length) if mainSum == n: return mid elif mainSum > n: high = mid - 1 else: low = mid + 1 return -1 def smallestGoodBase(self, n): n = int(n) for i in range(64, 0, - 1): x = self.check(n, i) if x >= 2: return str(x) return str(n - 1) ob = Solution() print(ob.smallestGoodBase("121"))इनपुट
"121"
आउटपुट
3