Python에서 가장 작은 좋은 기반

<시간/>

정수 n이 있다고 가정하고 n의 기본 k의 모든 자릿수가 1일 때 k>=2를 n의 좋은 밑이라고 부릅니다. 따라서 숫자 n이 문자열로 주어지면 n의 가장 작은 좋은 밑을 다음과 같이 반환해야 합니다. 끈. 따라서 숫자가 121이라면 답은 3이 됩니다. 3진법의 121은 11111이기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

getSum()이라는 메서드를 정의합니다. x와 길이가 필요합니다.
mainSum :=0 및 temp :=1로 설정
0 ~ length – 1 −
- mainSum :=mainSum + temp, temp :=temp * x
mainSum 반환
check()라는 메서드를 정의합니다. 이것은 n과 길이가 필요합니다 -
낮음 :=1, 높음 :=n
높은 동안>=낮음 -
- 중간 :=낮음 + (높음 – 낮음) / 2
- mainSum :=getSum(중간, 길이)
- mainSum =n이면 mid를 반환합니다.
- 그렇지 않으면 mainSum> n일 때 높음 :=mid – 1
- 그렇지 않으면 낮음 :=중간 + 1
반환 -1
메인 방법에서 다음을 수행하십시오 -
n :=주어진 숫자
64에서 0까지의 범위에 있는 i의 경우
- x :=체크(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”

Python에서 가장 작은 좋은 기반

예

입력

출력