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.c | |
parent | 8f4256dd97fe3ad442443201a9b893de80859c96 (diff) | |
download | leetcode-550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e.tar.gz leetcode-550458b5ef4a31e8c95e4fcd0f22bc6ca59fd46e.zip |
397. integer replacement
Diffstat (limited to 'integer_replacement.c')
-rw-r--r-- | integer_replacement.c | 31 |
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 +} |