leetcode

commit 675024decebe2a0bee4fe08ff5d635fe20ea061c
parent 9c151bc51e2f3a1ee54400c9930ee045122011e2
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 25 Feb 2026 20:46:12 -0700

1404. number of steps to reduce a number in binary representation to one

Diffstat:
M
num_steps_reduct_num.c
 | 
46
+++++++++++++++++-----------------------------
M
num_steps_reduct_num.py
 | 
25
+++++++++++--------------

2 files changed, 28 insertions(+), 43 deletions(-)
diff --git a/num_steps_reduct_num.c b/num_steps_reduct_num.c
@@ -10,38 +10,26 @@
  */
 
 int numSteps(char *s) {
-  int n = strlen(s), k = n / 2;
-  char *tmp = (char *)malloc((n + k + 1) * sizeof(char));
-  for (int i = 0; i < k; i++)
-    tmp[i] = '0';
-  strncpy(&tmp[k], s, n + 1);
-  int l = k, r = n + k - 1, step = 0;
-  while (l != r) {
-    if (tmp[r] == '0')
-      r--;
-    else if (tmp[r] == '1') {
-      tmp[r] = '0';
-      int m = r - 1;
-      while (1) {
-        if (tmp[m] == '0') {
-          tmp[m] = '1';
-          if (m < l)
-            l = m;
-          break;
-        } else {
-          tmp[m] = '0';
-        }
-        m--;
-      }
-    }
-    step++;
+  int n = strlen(s), ops = 0, carry = 0;
+  for (int i = n - 1; i > 0; i--) {
+    if (((s[i] - '0') + carry) % 2) {
+      ops += 2;
+      carry = 1;
+    } else
+      ops++;
   }
-  return step;
+  return ops + carry;
 }
 
 int main() {
   char *s1 = "1101", *s2 = "10", *s3 = "1";
-  printf("%d\n", numSteps(s1)); // expect: 6
-  printf("%d\n", numSteps(s2)); // expect: 1
-  printf("%d\n", numSteps(s3)); // expect: 0
+  int r1 = numSteps(s1);
+  int r2 = numSteps(s2);
+  int r3 = numSteps(s3);
+  printf("%d\n", r1); // expect: 6
+  assert(r1 == 6);
+  printf("%d\n", r2); // expect: 1
+  assert(r2 == 1);
+  printf("%d\n", r3); // expect: 0
+  assert(r3 == 0);
 }
diff --git a/num_steps_reduct_num.py b/num_steps_reduct_num.py
@@ -9,24 +9,21 @@ test cases.
 """
 
 
-class Solution(object):
-    def numSteps(self, s):
-        """
-        :type s: str
-        :rtype: int
-        """
-        ans, carry, n = 0, 0, len(s)
+class Solution:
+    def numSteps(self, s: str) -> int:
+        n, ops, carry = len(s), 0, 0
         for i in range(n - 1, 0, -1):
-            if int(s[i]) + carry == 1:
+            digit = int(s[i]) + carry
+            if digit % 2 == 1:
+                ops += 2
                 carry = 1
-                ans += 2
             else:
-                ans += 1
-        return ans + carry
+                ops += 1
+        return ops + carry
 
 
 if __name__ == "__main__":
     obj = Solution()
-    print(obj.numSteps("1101"))
-    print(obj.numSteps("10"))
-    print(obj.numSteps("1"))
+    print(obj.numSteps(s="1101"))
+    print(obj.numSteps(s="10"))
+    print(obj.numSteps(s="1"))