Number of Steps to Reduce a Binary Number to One
Deloitte● MediumFULLTIMEOAProblem statement
You are given a binary string binary representing a positive integer.
Repeatedly apply the following rule until the value becomes 1:
- If the current value is even, divide it by
2. - If the current value is odd, add
1.
Return the number of operations performed.
The binary string may be too long for a built-in integer type, so process it without converting the complete value to an integer.
Function
numSteps(binary: String) → intExamples
Example 1
binary = "1101"return = 6The values are 13 -> 14 -> 7 -> 8 -> 4 -> 2 -> 1, which uses 6 operations.
Example 2
binary = "10"return = 1The value 2 is even, so one division produces 1.
Example 3
binary = "1"return = 0The value is already 1, so no operation is needed.
Constraints
1 <= binary.length <= 500.binarycontains only0and1.binary[0] == '1'.