Problem: Given a positive integer n, in a single operation, choose any i >= 0 and convert n to n 2^i or n - 2^i. Find the minimum number of operations required to convert n to 0. Example, n = 5. n can be reduced to 0 in two operations: 5 - 2^0 - 2^2 = 0.

My solution that works for every case I've tested by hand:

def get_min_operations(n: int) -> int:
    binary_representation = "{0:b}".format(n)
    # reverse the string so i = 0 is the least significant bit
    binary_representation = binary_representation[::-1]
    for i, bit in enumerate(binary_representation):
        if bit == "0":
            continue
        if (i == len(binary_representation) - 1) or binary_representation[i   1] == "0": # isolated 1
            return 1   get_min_operations(n - 2 ** i)
        else: # neighboring 1s
            return 1   get_min_operations(n   2 ** i)
    return 0

This iteratively applies operations to flip the 1s in the binary representation of the number until it is all 0s. It's not necessary for this to be recursive.

Here are my test cases:

    assert(get_min_operations(1) == 1)
    assert(get_min_operations(2) == 1)
    assert(get_min_operations(3) == 2)
    # 4 -2^2 == 0
    assert(get_min_operations(4) == 1)
    # 5 - 2^0   2^2 == 0
    assert(get_min_operations(5) == 2)
    # 6   2^1 - 2^3 == 0
    assert(get_min_operations(6) == 2)
    # 7   2^0 - 2^3 == 0
    assert(get_min_operations(7) == 2)
    assert(get_min_operations(8) == 1)
    # 9 - 2^0 - 2^3 == 0
    assert(get_min_operations(9) == 2)
    # 10 - 2^1 - 2^3 == 0
    assert(get_min_operations(10) == 2)
    # 11 - 2^0 - 2^1 - 2^3 == 0
    assert(get_min_operations(11) == 3)
    # 12 - 2^2 - 2^3 == 0
    assert(get_min_operations(12) == 2)
    # 13 - 2^0 - 2^2 - 2^3 == 0
    assert(get_min_operations(13) == 3)
    # 14   2^2 - 2^4 == 0
    assert(get_min_operations(14) == 2)
    assert(get_min_operations(16) == 1)
    # 18 - 2 - 16 == 0
    assert(get_min_operations(18) == 2)
    assert(get_min_operations(21) == 3)
    # 24   8 - 32 == 0
    assert(get_min_operations(24) == 2)
    # 26   2   4 - 32 == 0
    assert(get_min_operations(26) == 3)
    assert(get_min_operations(27) == 3)
    # Add 2^2 == 4, subtract 2^5 == 32
    assert(get_min_operations(28) == 2)

Many programmers on first inspection of this problem, think it can be solved using dynamic programming with just the -2^i operations, or, even simpler, they think the solution is the Hamming weight, but see how these approaches fail:

Notice that 7 can be reduced to 0 in only two operations, not 3! Adding 1 makes it a power of 2 and can then be reduced to 0 in one additional operation for a total of 2. The idea of using the Hamming weight led to the working solution I have above. However, I don't have an intuition for it or what types of problems this bit manipulation would broadly apply to. I would greatly prefer if I could come up with some dynamic programming or number theory solution to this problem.

CodePudding user response：

I believe this can be achieved using string manipulations on the bit representation of the number.

Removing a stand-alone "1" can be done in one operation. Any streak of 1s can be removed in two operations, no matter the length of the streak (i.e. adding 1 at the lowest power and then removing 1 at the next higher power).

The only exception to this would be lone 0s between 1s in 4 bits or more (i.e. ..1011.. or ..1101..) where flipping the 0 (in one operation) allows the removal of the 3 or more 1 bits in exactly 3 moves which is equal or better than the 3-4 operations to remove two separate streaks of 1s.

Any streak of multiple zeros isolates the 1s sufficiently to be processed as separate problems.

from itertools import groupby
def get_min_operations(n):
    result = 0
    bits = f"{n:b}"
    for shortcut in ("1011","1101"):
        result  = bits.count(shortcut) 
        bits    = bits.replace(shortcut,"1111")
    result  = sum( 1 (len(g)>1) for b,(*g,) in groupby(bits) if b=="1")
    return result

CodePudding user response：

You want to convert to a "signed" binary representation where instead of just 0's and 1's, you also include -1's (which I represent as '-')

from math import log, ceil, floor

def signed_binary(num, current_digit = None):
    if num == 0:
        return '0' if current_digit is None else '0'*current_digit   '0'
    elif num == 1:
        return '1' if current_digit is None else '0'*current_digit   '1'
    elif num == -1:
        return '-' if current_digit is None else '0'*current_digit   '-'
    else:
        if num > 0:
        
            # Got log base 2
            power = log(num)/log(2)

            # Look to represent as either 2^ceil(power) - remainder
            # or 2^floor(power) - remainder
            # and use representations with lower number of '1' and '-'
            
            # Check if we need to prepend zeros
            if current_digit is not None:
                ceil_start = '0'*max(0, current_digit - ceil(power))   '1'
                floor_start = '0'*max(0, current_digit - floor(power))   '1'
                
            else:
                ceil_start = '1'
                floor_start = '1'
                
            return shorter_rep(ceil_start   signed_binary(num - 2**ceil(power), ceil(power)-1), floor_start   signed_binary(num - 2**floor(power), floor(power)-1))
        
        else:
            return flip_signed_binary(signed_binary(-num))
    
def shorter_rep(sbin1, sbin2):
    
    if sbin1.count('1')   sbin1.count('-') < sbin2.count('1')   sbin2.count('-'):
        return sbin1
    else:
        return sbin2
    
def flip_signed_binary(sbin):
    return ''.join(['-' if char == '1' else '1' if char == '-' else char for char in sbin])


for i in range(30):
    rep = signed_binary(i)
    ops = rep.count('1')   rep.count('-')
    print(f'{i}: \'{rep}\', {ops} operations')