CODEWITHSUNDEEP
pythonoptimizationbitwise-operators
zelda26
zelda26

Reputation: 489

fastest way to minimize n as per given condition in python

how can i make the following code faster? the input is a binary string and i am converting it to a number. possibly i need to use the binary string instead of the number? the algorithm may only divide by 2 or subtract 1 from the input. I tried the code below and it is not fast enough.

I tried the below:

def steps_to_zero(n) : 

    n=int(n,2)
    count = 0
    while n > 0:
        if n % 2 == 0:            
            n = n // 2
        else:  
            n = n - 1

        count += 1
    return (count)

It must be twice as fast as this:

def steps_to_zero_v1(x):
    x_int = int(x,2)
    steps = 0
    while x_int != 0:
        if x_int % 2 == 0:
            x_int = x_int // 2 
        else:
            x_int = x_int - 1
        steps += 1
    return steps

Upvotes: 1

Views: 511

Answers (2)

Energya
Energya

Reputation: 2673

Your proposed code is doing exactly the same as the given code. The main thing you want to look into to speed it up is getting rid of the expensive if n % 2 == 0 test.

The solution is that you can reason about this problem on the bit-level without having to do any brute-force calculations.

For the trivial case n=0 we get count=0. For the next simpler case n=1 we only have to subtract 1 once, leading to count=1.

In all other cases, we're dealing with some longer binary number. If the last digit of that number is a 0, we can divide by 2 to make our binary number a digit shorter:

...x0 / 2 = ...x  # 1 step for 1 digit shorter

Otherwise we have to subtract 1 first before we can divide by two.

...x1 - 1 = ...x0
...x0 / 2 = ...x   # 2 steps for 1 digit shorter

In other words: for the left-most 1 we need 1 operation, for all digits we need 1 if it's 0, and 2 if it's a 1.

This means that you can calculate this simply by counting the number of 1's in your string:

def steps_to_zero(n):
    n = n.lstrip('0')            # remove leading zeroes if they occur
    divisions = len(n) - 1       # don't have to divide for the left-most 1
    subtractions = n.count('1')  # each 1 needs a subtraction to become a 0
    return divisions + subtractions

Timing comparison between % 2 and .count('1') averaged over 0-10,000:

# % 2
$ python3 -m timeit -s "x=list(range(10000))" "[y%2 for y in x]"
1000 loops, best of 3: 277 usec per loop

# .count('1')
$ python3 -m timeit -s "x=[bin(i) for i in range(10000)]" "[y.count('1') for y in x]"
1000 loops, best of 3: 1.35 msec per loop

Although .count('1') is ~5x slower than %2 per execution, the .count('1') only has to be performed once, while %2 has to be performed log2(n) times. This makes the .count('1') approach faster when n > 2**5 (=32).

Upvotes: 5

Eugene Yarmash
Eugene Yarmash

Reputation: 149736

Instead of converting the string to a number and performing expensive division and modulo operations, simply process it bit by bit. For each 1 bit except the leftmost one you'll need two steps (subtraction and division), and for each 0 bit you'll need one step (division):

def steps_to_zero(n):
    count = 0
    for x in n.lstrip('0'):
        if x == '1':
            count += 2
        else:
            count += 1
    return count - 1

Or, if you prefer one-liners:

def steps_to_zero(n):
    return sum((x == '1') + 1 for x in n.lstrip('0')) - 1

Upvotes: 4

Related Questions