Discussion on: Daily Challenge #152 - Strongest Number in an Interval

[Kermit Alexander II]

One way to be sneaky about solving this problem comes from realizing what the problem is asking for when it says to "divide by 2 until we reach an odd number." If you think about the binary representation of an integer, there's only one way for it to be odd - that is, for its lowest/least-significant bit to be set to 1. Also recalling that dividing by two is equivalent to a single bitshift to the right, we can find a neat trick.

With 12 as an example, we can see that in binary it is 1100, so it would take two bitshifts right for it to be odd - that is, to turn it into 11 (3). So we don't need to actually divide 12 until we get 3, but simply count the number of trailing zeroes in 12 and use that as its strength - which would be 2, in this case. From there, we just need to keep track of the largest-strength-with-smallest-number combo and we'll be fine. With all that said, here's that strategy implemented in Python:

#!/usr/bin/env python3


def trailing_zeroes(num):
    num_trailing = 0
    while num & 1 == 0:
        # loop/bitshift right until we find a nonzero bit
        num_trailing += 1
        num = num >> 1
    return num_trailing


def find_strongest(start, stop):
    """Return the strongest number in a closed interval as per dev.to challenge #152
    """
    max_strength = 0
    best_num = 0
    # add 1 to halt the loop at the value of stop, not stop - 1
    for i in range(start, stop + 1):
        if i % 2 == 1:
            # don't bother with odd numbers
            continue
        # the strength given in the spec can be expressed
        # as the number of trailing zeroes in the number
        strength = trailing_zeroes(i)
        if strength > max_strength:
            max_strength = strength
            best_num = i
        elif strength == max_strength:
            # as per the spec, choose the lower number
            best_num = min(best_num, i)
    return best_num


if __name__ == "__main__":
    print(find_strongest(1, 2))
    print(find_strongest(5, 10))
    print(find_strongest(48, 56))
    print(find_strongest(129, 193))

edit/take #2: I tried to think about a way to optimize the trailing zero calculation for a while, but couldn't come up with anything; so I gave up and decided to search around a little bit to find if anyone came up with an O(1) method to calculate the trailing-zero problem instead of the naive linear solution I posted. Turns out someone did, and the link can probably explain better than I. The result of integrating that solution with the code I posted earlier is below:

#!/usr/bin/env python3


# the below function is adapted from https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup
def trailing_zeroes_fast(num):
    lookup = [32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30,
              28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15,
              29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18]
    num_trailing = lookup[(-num & num) % 37]
    return num_trailing


def find_strongest(start, stop):
    """Return the strongest number in a closed interval as per dev.to challenge #152
    """
    max_strength = 0
    best_num = 0
    # add 1 to halt the loop at the value of stop, not stop - 1
    for i in range(start, stop + 1):
        if i % 2 == 1:
            # don't bother with odd numbers
            continue
        # the strength given in the spec can be expressed
        # as the number of trailing zeroes in the number
        strength = trailing_zeroes_fast(i)
        if strength > max_strength:
            max_strength = strength
            best_num = i
        elif strength == max_strength:
            # as per the spec, choose the lower number
            best_num = min(best_num, i)
    return best_num


if __name__ == "__main__":
    print(find_strongest(1, 2))
    print(find_strongest(5, 10))
    print(find_strongest(48, 56))
    print(find_strongest(129, 193))

As a sidenote, an alternative method to count trailing zeroes to is to use the base 2 log of (-num & num), i.e, math.log2(num & -num) - in essence, this is asking how many bitshifts left starting from 1 are needed to hit the first set bit of num - but while it's clearly shorter and definitely more understandable, I don't believe this is faster than the lookup table route.