Sponsored
Sponsored
This approach involves simulating the reduction steps performed directly on the binary number string. We traverse the binary string backwards, simulating each step based on whether the current number is odd or even. Additionally, whenever we encounter a carry after incrementing an odd number, we propagate the carry to handle the necessary binary addition.
Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), only a constant amount of extra space is used.
1class Solution {
2 public int numSteps(String s) {
3 int steps = 0, carry = 0;
4 for (
This Java implementation uses similar logic as in C++ and C#. Character manipulation is used to decode binary and manage the carry as needed for calculation of steps.
Convert the binary representation to a decimal integer, then simulate the operations using intuitive arithmetic operations. This approach avoids character-level string manipulations.
Time Complexity: O(n) for initial conversion, O(log m) for operations (where m is the integer value).
Space Complexity: O(1), after input conversion.
public class Solution {
public int NumSteps(string s) {
long num = Convert.ToInt64(s, 2);
int steps = 0;
while (num > 1) {
if (num % 2 == 0) {
num /= 2;
} else {
num += 1;
}
steps++;
}
return steps;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.NumSteps("1101")); // Output: 6
}
}The C# method uses Convert.ToInt64 for the translation from binary to decimal. Subsequent loop reductions process arithmetic steps based on the remainder parity check until the number achieves a value of 1.