aboutsummaryrefslogtreecommitdiff
path: root/integer_replacement.c
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.c
parent8f4256dd97fe3ad442443201a9b893de80859c96 (diff)
downloadleetcode-550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e.tar.gz
leetcode-550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e.zip
397. integer replacement
Diffstat (limited to 'integer_replacement.c')
-rw-r--r--integer_replacement.c31
1 files changed, 31 insertions, 0 deletions
diff --git a/integer_replacement.c b/integer_replacement.c
new file mode 100644
index 0000000..8a3fdb8
--- /dev/null
+++ b/integer_replacement.c
@@ -0,0 +1,31 @@
+// 397. Integer Replacement
+#include "leetcode.h"
+
+/*
+ * 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
+ */
+
+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--;
+ ans++;
+ }
+ return ans;
+}
+
+int main() {
+ printf("%d\n", integerReplacement(8)); // expect: 3
+ printf("%d\n", integerReplacement(7)); // expect: 4
+ printf("%d\n", integerReplacement(4)); // expect: 2
+}