aboutsummaryrefslogtreecommitdiff
path: root/num_steps_reduct_num.c
diff options
context:
space:
mode:
Diffstat (limited to 'num_steps_reduct_num.c')
-rw-r--r--num_steps_reduct_num.c47
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
+}