diff options
Diffstat (limited to 'num_steps_reduct_num.c')
-rw-r--r-- | num_steps_reduct_num.c | 47 |
1 files changed, 47 insertions, 0 deletions
diff --git a/num_steps_reduct_num.c b/num_steps_reduct_num.c new file mode 100644 index 0000000..78bfb53 --- /dev/null +++ b/num_steps_reduct_num.c @@ -0,0 +1,47 @@ +// 1404. Number of Steps to Reduce a Number in Binary Representation to One +#include "leetcode.h" + +/* + * given the binary representation of an integer as a string 's', return the + * number of steps to reduce it to 1 under the following rules. if the current + * number is even, you have to divide it by 2. if the current number is odd, you + * have to add 1 to it. it is guaranteed that you can always reach one for all + * test cases. + */ + +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++; + } + return step; +} + +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 +} |