1342. Number of Steps to Reduce a Number to Zero
Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 85.7%
Problem Breakdown
The problem requires us to reduce a given non-negative integer num to zero by performing specific operations. If the number is even, we divide it by 2; if it’s odd, we subtract 1 from it. The goal is to determine the total number of steps required to reach zero.
Inputs:
- A non-negative integer
num(0 <= num <= 10^6).
Outputs:
- An integer representing the number of steps needed to reduce
numto zero.
Implicit Constraints or Tricky Edge Cases:
- The input can be zero, which requires zero steps.
- The input is guaranteed to be a non-negative integer within a specific range, so we don’t need to handle negative numbers or overflow.
Intuition
A brute-force approach would involve repeatedly checking if the number is even or odd and performing the corresponding operation until the number becomes zero. This approach is straightforward but has a time complexity of O(log n) because each division by 2 reduces the number of bits needed to represent it by one.
The key insight here is that we can leverage bit manipulation to optimize the process. Specifically, we can use bitwise operations to determine if a number is even or odd and to perform the division operation efficiently.
Approach
- Initialize a counter
stepsto zero. - Iterate while
numis greater than zero:- If
numis even (i.e., the least significant bit is 0), divide it by 2 using a right shift (num >>= 1). - If
numis odd (i.e., the least significant bit is 1), subtract 1 from it. - Increment the
stepscounter after each operation.
- If
- Return the
stepscounter oncenumreaches zero.
This approach uses bitwise operations, which are generally faster than arithmetic operations, making it more efficient.
Complexity Analysis
- Time Complexity: O(log n), where n is the input number. This is because each division by 2 reduces the number of bits needed to represent the number by one.
- Space Complexity: O(1), as we only use a constant amount of extra space for the
stepscounter.
Solution
def numberOfSteps(num: int) -> int:
steps = 0
while num > 0:
if num % 2 == 0:
num >>= 1 # Divide by 2 using right shift
else:
num -= 1 # Subtract 1 for odd numbers
steps += 1
return steps
Edge Cases Handled
- Zero Input: If
numis zero, the loop does not execute, and the function returns 0 immediately. - Small Numbers: The approach works efficiently even for small numbers like 1 or 2.
- Large Numbers: Given the constraints (0 <= num <= 10^6), the solution handles large numbers within the specified range without performance issues.