aboutsummaryrefslogtreecommitdiff
path: root/integer_replacement.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-11 11:38:29 -0600
committerJack Sangdahl <[email protected]>2025-03-11 11:38:29 -0600
commit550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e (patch)
tree4e59b809251fa6ffc69945a1c2bb2421a145c209 /integer_replacement.py
parent8f4256dd97fe3ad442443201a9b893de80859c96 (diff)
downloadleetcode-550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e.tar.gz
leetcode-550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e.zip
397. integer replacement
Diffstat (limited to 'integer_replacement.py')
-rw-r--r--integer_replacement.py33
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))