diff options
author | Jack Sangdahl <[email protected]> | 2025-03-11 11:38:29 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-11 11:38:29 -0600 |
commit | 550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e (patch) | |
tree | 4e59b809251fa6ffc69945a1c2bb2421a145c209 /integer_replacement.py | |
parent | 8f4256dd97fe3ad442443201a9b893de80859c96 (diff) | |
download | leetcode-550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e.tar.gz leetcode-550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e.zip |
397. integer replacement
Diffstat (limited to 'integer_replacement.py')
-rw-r--r-- | integer_replacement.py | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/integer_replacement.py b/integer_replacement.py new file mode 100644 index 0000000..8d7dbda --- /dev/null +++ b/integer_replacement.py @@ -0,0 +1,33 @@ +# 397. Integer Replacement + +""" +given a positive integer 'n', you can apply one of the following operations: +if 'n' is even, replace 'n' witn 'n / 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 +""" + + +class Solution(object): + def integerReplacement(self, n): + """ + :type n: int + :rtype: int + """ + ans = 0 + while n > 1: + ans += 1 + if n % 2 == 0: + n //= 2 + elif n % 4 == 1 or n == 3: + n -= 1 + else: + n += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.integerReplacement(n=8)) + print(obj.integerReplacement(n=7)) + print(obj.integerReplacement(n=4)) |