leetcode

commit aad28e15e172b1eb113ca671ce42a081e81ae738
parent 318857f0b9cb76b323227784a6d6483a3b2f01cb
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 30 Oct 2025 08:50:16 -0600

397. integer replacement

Diffstat:
M
integer_replacement.c
 | 
19
++++++++++---------
M
integer_replacement.py
 | 
22
++++++++++++----------

2 files changed, 22 insertions(+), 19 deletions(-)
diff --git a/integer_replacement.c b/integer_replacement.c
@@ -10,15 +10,16 @@
 
 int integerReplacement(int n) {
   int ans = 0;
-  while (n > 1) {
-    if (n == 3)
-      return ans + 2;
-    else if (!(n & 1))
-      n = (n >> 1) & 0x7FFFFFFF;
-    else if (!((n + 1) % 4))
-      n++;
-    else
-      n--;
+  long long num = n;
+  while (num > 1) {
+    if (!(num & 1))
+      num >>= 1;
+    else {
+      if (num == 3 || !((num >> 1) & 1))
+        num--;
+      else
+        num++;
+    }
     ans++;
   }
   return ans;
diff --git a/integer_replacement.py b/integer_replacement.py
@@ -9,21 +9,23 @@ either 'n + 1' or 'n - 1'. return the minimum number of operations needed for
 
 
 class Solution(object):
+    def helper(self, x, y=0):
+        if x == 1:
+            return y
+        if x % 2 == 0:
+            return self.helper(x >> 1, y + 1)
+        else:
+            if x == 3 or not ((x >> 1) & 1):
+                return self.helper(x - 1, y + 1)
+            else:
+                return self.helper(x + 1, y + 1)
+
     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
+        return self.helper(n)
 
 
 if __name__ == "__main__":