大整数转二进制求最小步数算法的错误排查求助

需求与实现思路 #

需要处理最大为9^309的整数，用Python 2.7实现通过加1、减1、偶数时除以2三种操作，计算从该数到1的最小步数。我的实现策略如下：

• 将数字转换为二进制形式
• 当数字不等于'1'时循环：
  • 若末位为0则除以2
  • 若末位为1且倒数第二位也为1则加1（3除外）
  • 若末位为1且倒数第二位为0则减1

我的实现代码 #

def compare_nums(n, pow_2_num):
    """Checks n >= pow_2_num. returns -1 if false, 0 if equal, or else 1"""
    if (n == pow_2_num):
        return (0)
    if (len(n) == len(pow_2_num)):
        return (1 if n > pow_2_num else -1)
    if (len(n) > len(pow_2_num)):
        return (1)
    return (-1)

def max_pow_2(n):
    """returns a positive integer x, such that n >= 2^x"""
    pow_2_num = 1
    x = 0
    while (True):
        pow_2_num *= 2
        res = compare_nums(n, str(pow_2_num))
        if res != -1:
            x += 1
        if res != 1:
            return x

def raise_2(pow_2):
    """returns 2^pow_2 as a string"""
    if (pow_2 == 0):
        return ('1')
    num = '1'
    for _ in range(pow_2):
        carry = 0
        temp = ''
        for i in range(len(num) - 1, -1, -1):
            prod = int(num[i]) * 2 + carry
            carry = prod // 10
            temp = str(prod % 10) + temp
        if carry:
            temp = str(carry) + temp
        num = temp
    return (num.lstrip('0'))

def sub_num(n, pow_2):
    """returns n - 2^pow_2 in string form"""
    num_pow_2 = raise_2(pow_2)
    l_len = len(n)
    r_len = len(num_pow_2)
    borrowed = 0
    ans = ''
    # subract digit by digit moving left starting from end
    for i in range(r_len):
        l_curr = int(n[l_len - 1 - i]) - borrowed
        r_curr = int(num_pow_2[r_len - 1 - i])
        if l_curr >= r_curr:
            borrowed = 0
        else:
            l_curr += 10
            borrowed = 1
        ans = str(l_curr - r_curr) + ans
    sub_index = l_len - r_len - 1  # index in n, just before start of subtraction
    if borrowed:
        # find index of first nonzero going left from sub_index(inclusive)
        for i in range(sub_index, -1, -1):
            if n[i] != '0':
                break
        ans = n[:i] + str(int(n[i]) - 1) + '9' * (sub_index - i) + ans
    else:
        ans = n[:sub_index + 1] + ans
    ans = ans.lstrip('0')
    return (ans if ans else '0')

def generate_x_i_list(n):
    """creates a list of two's exponents equaling n.
    for  n = 2^i + 2^j ... + 2^k, such that i, j,...,k >= 0,
    returns [i, j, ... k]"""
    x_i_list = []
    while (True):
        pow_2 = max_pow_2(n)
        x_i_list.append(pow_2)
        n = sub_num(n, pow_2)
        if n == '0':
            break
    return (x_i_list)

def to_binary(n):
    """converts n to base 2 representation"""
    if n == '0':
        return ('0')
    x_i_list = generate_x_i_list(n)
    binary_len = int(x_i_list[0]) + 1
    n_binary = [0 for i in range(binary_len)]
    for pow_2 in x_i_list:
        n_binary[binary_len - 1 - pow_2] = 1
    n_binary = [str(i) for i in n_binary]
    return (''.join(n_binary))

def solution(n):
    """returns minimum no. of steps required to reach 1 starting from n.
    allowed steps: add or subtract 1, and divide by 2 if n is even"""

    n_binary = to_binary(n)
    step_count = 0
    while (n_binary != '1'):
        if (n_binary[-1] == '0'):  # divide by 2
            while (n_binary[-1] == '0'):
                n_binary = n_binary[:-1]
                step_count += 1
        elif (n_binary[-1] == '1'):
            if (n_binary[-2] == '1' and len(n_binary) > 2):  # > 2 to avoid adding one to 3 (0b11) 
                # add 1: change 1's to 0's, starting from end until 0 is found and changed to 1.
                # If no 0 is found (check first) add 1 at start
                zero_exists = n_binary.count('0')
                if zero_exists:
                    zero_index = n_binary.rindex('0')
                    aftr_0 = '0' * (len(n_binary) - 1 - zero_index)
                    bfr_0 = n_binary[:zero_index]
                    n_binary = bfr_0 + '1' + aftr_0
                else:
                    n_binary = '1' + ('0' * len(n_binary))
            else:
                # subtract 1: change last 1 to 0
                n_binary = n_binary[:-1] + '0'
            step_count += 1
    return (step_count)

对比的正确实现 #

StackOverflow上的以下函数可通过所有测试：

def stepCount(n):
    count = 0
    while n > 1:
        if n % 2 == 0:
            n = n // 2
        elif n == 3 or n % 4 == 1:
            n = n - 1
        else:
            n = n + 1
        count += 1
    return count

问题现状 #

我的代码运行后有半数测试用例失败，但无法查看测试输入。自行测试诸多边界用例均正常，且对比两个实现10^6以内的结果也未发现差异。请问我的解决方案失败的原因是什么？或者应该用哪些边界用例来定位错误？

内容的提问来源于stack exchange，提问作者Menelik Berhan