aboutsummaryrefslogtreecommitdiff
path: root/num_steps_reduct_num.c
blob: 78bfb535fc8b7a3dcf5366b945d2531b5d89c145 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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
}