Skip to content

1404. Number of Steps to Reduce a Number in Binary Representation to One 👍

  • Time: $O(n)$
  • Space: $O(1)$
 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
class Solution {
 public:
  int numSteps(string s) {
    int ans = 0;

    // All the trailing 0s can be popped by 1 step.
    while (s.back() == '0') {
      s.pop_back();
      ++ans;
    }

    if (s == "1")
      return ans;

    // `s` is now odd, so add 1 to `s` and cost 1 step.
    ++ans;

    // All the 1s will become 0s and can be popped by 1 step.
    // All the 0s will become 1s and can be popped by 2 steps (adding 1 then
    // dividing by 2).
    for (const char c : s)
      ans += c == '1' ? 1 : 2;

    return ans;
  }
};

 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
class Solution {
  public int numSteps(String s) {
    int ans = 0;
    StringBuilder sb = new StringBuilder(s);

    // All the trailing 0s can be popped by 1 step.
    while (sb.charAt(sb.length() - 1) == '0') {
      sb.deleteCharAt(sb.length() - 1);
      ++ans;
    }

    if (sb.toString().equals("1"))
      return ans;

    // `s` is now odd, so add 1 to `s` and cost 1 step.
    ++ans;

    // All the 1s will become 0s and can be popped by 1 step.
    // All the 0s will become 1s and can be popped by 2 steps (adding 1 then
    // dividing by 2).
    for (final char c : sb.toString().toCharArray())
      ans += c == '1' ? 1 : 2;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def numSteps(self, s: str) -> int:
    ans = 0
    chars = list(s)

    # All the trailing 0s can be popped by 1 step.
    while chars[-1] == '0':
      chars.pop()
      ans += 1

    if ''.join(chars) == '1':
      return ans

    # `s` is now odd, so add 1 to `s` and cost 1 step.
    # All the 1s will become 0s and can be popped by 1 step.
    # All the 0s will become 1s and can be popped by 2 steps (adding 1 then
    # dividing by 2).
    return ans + 1 + sum(1 if c == '1' else 2 for c in chars)