[leetCode] 397. Integer Replacement (Python)

Given a positive integer n, you can apply one of the following operations:

1. If n is even, replace n with n / 2.
2. If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

 

Example 1:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1

Example 3:

Input: n = 4
Output: 2

 

Constraints:

• 1 <= n <= 231 - 1

첫 번째 시도 ( 시간 초과 )

class Solution:
    def integerReplacement(self, n: int) -> int:
        cnt = 0
        cnt2 = 0
        n2 = n
        
        while True:
            if n == 1:
                break
            else:
                if n % 2 == 1:
                    n = n -1
                    cnt = cnt + 1
                    
                elif n % 2 == 0:
                    n = n // 2
                    cnt = cnt + 1
                    
        while True:
            if n2 == 1:
                break
            else:
                if n % 2 == 1:
                    n2 = n2 + 1
                    cnt2 = cnt2 + 1
                    
                elif n % 2 == 0:
                    n2 = n2 // 2
                    cnt2 = cnt2 + 1
        
        return min([cnt, cnt2])

첫번째 시도는 먼저 홀수일 경우 - 1 을 하면서 짝수일 경우 2로 나눈 방법과

홀수일 경우 +1을 하면서 짝수일 경우 2로 나눈 방법 2가지 방법 중 더 적은 횟수를 정답으로 설정했습니다.

 

Solution

class Solution:
    def integerReplacement(self, n: int) -> int:
        cnt = 0
        
        while True:
            if n == 1:
                break
            elif n == 3:
                return cnt + 2
            else:
                if n % 2 == 1:
                    if ((n-1) // 2) % 2 == 1:
                        n = n + 1
                    else:
                        n = n -1
                    cnt = cnt + 1
                    
                elif n % 2 == 0:
                    n = n // 2
                    cnt = cnt + 1
                    
        return cnt

이번에는 -1 방식 +1 방식을 모두 해보는 것이 아니라

-1로 뺐을때의 숫자가 2로 나누었을때 홀수일 경우 +1을 하고 그렇지 않을 경우 -1을 하도록 했습니다.

SOMJANG/CODINGTEST_PRACTICE