unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1404: Number of Steps to Reduce a Number in Binary Representation to One

link

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def numSteps(self, s: str) -> int:
        # convert s into int
        n = 0
        for c in s:
            d = 1 if c == '1' else 0
            n = 2*n + d
        # simulate and count
        steps = 0
        while n != 1:
            if n%2 == 0:
                n //= 2
            else:
                n += 1
            steps += 1
        return steps

Observations

  1. We can simulate the operations one digit at a time.
  2. If we start with an even number like 12, we divide by 2 and end up with 6. End result here is a right shifted number. On the other hand, if we start with an odd number like 11, we first add 1 to make it 12, then we divide by 2 and end up with 6. End result here is again a right shifted number but after two operations instead of one.
  3. Since we are supposed to stop when the number is 1, we may have processed one digit too many. So, we may need to correct the step_count, like in the case below. So, we keep track of prev_carry as well.
class Solution:
    def numSteps(self, s: str) -> int:
        step_count = 0
        prev_carry, carry = 0, 0
        for i in range( len(s)-1, -1, -1 ):
            curr_sum = (1 if s[i] == '1' else 0) + carry
            curr_digit = 1 if curr_sum == 1 else 0
            prev_carry = carry
            carry = 0 if curr_sum == 0 else 1

            if curr_digit == 0: # right shift
                step_count += 1
            else: # add 1 and right shift
                step_count += 2
        
        return step_count if prev_carry else step_count-2

Or, more concisely:

class Solution:
    def numSteps(self, s: str) -> int:
        step_count = 0
        prev_carry, carry = 0, 0
        for i in range( len(s)-1, -1, -1 ):
            prev_carry = carry
            carry, curr_digit = divmod(int(s[i])+prev_carry, 2)

            if curr_digit == 0: # right shift
                step_count += 1
            else: # add 1 and right shift
                carry = 1 # effect of add 1
                step_count += 2
        
        return step_count if prev_carry else step_count-2

tanvirdotzaman

Leave a comment