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
1to 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 <= 500sconsists of characters '0' or '1's[0] == '1'
Solutions
This solution converts the binary string to an array for efficient manipulation, then repeatedly either pops the last '0' or performs addition by finding the rightmost '0' and flipping all trailing '1's to '0's while propagating a carry back to that position.
Language: javascript(2026-02-26 09:30)DONE
CPU Performance100.00%
Memory Performance89.41%
/**
* @param {string} s
* @return {number}
*/
var numSteps = function(s) {
const arr = s.split('');
let res = 0;
while (arr.length > 1) {
res++;
if (arr[arr.length - 1] === '0') {
arr.pop();
continue;
}
let carry = 1;
for (let i = arr.length - 1; i >= 0; i--) {
if (arr[i] === '0') {
arr[i] = '1';
carry = 0;
break;
}
arr[i] = '0';
}
if (carry) {
arr.unshift('1');
}
}
return res;
};