Skip to content

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

Description

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.

Β 

Example 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14.Β 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.Β  
Step 5) 4 is even, divide by 2 and obtain 2.Β 
Step 6) 2 is even, divide by 2 and obtain 1.Β 

Example 2:

Input: s = "10"
Output: 1
Explanation: "10" corresponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.Β 

Example 3:

Input: s = "1"
Output: 0

Β 

Constraints:

  • 1 <= s.lengthΒ <= 500
  • s consists of characters '0' or '1'
  • s[0] == '1'

Solutions

Solution 1: Simulation

We simulate operations \(1\) and \(2\), while maintaining a carry \(\textit{carry}\) to indicate whether there is a current carry. Initially, \(\textit{carry} = \text{false}\).

We traverse the string \(s\) from the end toward the beginning:

  • If \(\textit{carry}\) is \(\text{true}\), the current bit \(c\) needs to be incremented by \(1\). If \(c\) is \(0\), it becomes \(1\) after adding \(1\), and \(\textit{carry}\) becomes \(\text{false}\); if \(c\) is \(1\), it becomes \(0\) after adding \(1\), and \(\textit{carry}\) remains \(\text{true}\).
  • If \(c\) is \(1\), we need to perform operation \(1\), i.e., add \(1\), and \(\textit{carry}\) becomes \(\text{true}\).
  • At this point \(c\) is \(0\), so we need to perform operation \(2\), i.e., divide by \(2\).

After the traversal, if \(\textit{carry}\) is still \(\text{true}\), we need to perform operation \(1\) one more time.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

 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:
        carry = False
        ans = 0
        for c in s[:0:-1]:
            if carry:
                if c == '0':
                    c = '1'
                    carry = False
                else:
                    c = '0'
            if c == '1':
                ans += 1
                carry = True
            ans += 1
        if carry:
            ans += 1
        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) {
        boolean carry = false;
        int ans = 0;
        for (int i = s.length() - 1; i > 0; --i) {
            char c = s.charAt(i);
            if (carry) {
                if (c == '0') {
                    c = '1';
                    carry = false;
                } else {
                    c = '0';
                }
            }
            if (c == '1') {
                ++ans;
                carry = true;
            }
            ++ans;
        }
        if (carry) {
            ++ans;
        }
        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
class Solution {
public:
    int numSteps(string s) {
        int ans = 0;
        bool carry = false;
        for (int i = s.size() - 1; i; --i) {
            char c = s[i];
            if (carry) {
                if (c == '0') {
                    c = '1';
                    carry = false;
                } else
                    c = '0';
            }
            if (c == '1') {
                ++ans;
                carry = true;
            }
            ++ans;
        }
        if (carry) ++ans;
        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
func numSteps(s string) int {
    ans := 0
    carry := false
    for i := len(s) - 1; i > 0; i-- {
        c := s[i]
        if carry {
            if c == '0' {
                c = '1'
                carry = false
            } else {
                c = '0'
            }
        }
        if c == '1' {
            ans++
            carry = true
        }
        ans++
    }
    if carry {
        ans++
    }
    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
27
28
29
30
function numSteps(s: string): number {
    let ans = 0;
    let carry = false;

    for (let i = s.length - 1; i > 0; i--) {
        let c = s[i];

        if (carry) {
            if (c === '0') {
                c = '1';
                carry = false;
            } else {
                c = '0';
            }
        }

        if (c === '1') {
            ans++;
            carry = true;
        }

        ans++;
    }

    if (carry) {
        ans++;
    }

    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
27
28
29
30
31
32
33
impl Solution {
    pub fn num_steps(s: String) -> i32 {
        let bytes = s.as_bytes();
        let mut ans: i32 = 0;
        let mut carry = false;

        for i in (1..bytes.len()).rev() {
            let mut c = bytes[i];

            if carry {
                if c == b'0' {
                    c = b'1';
                    carry = false;
                } else {
                    c = b'0';
                }
            }

            if c == b'1' {
                ans += 1;
                carry = true;
            }

            ans += 1;
        }

        if carry {
            ans += 1;
        }

        ans
    }
}

Comments