Common Operations

x.bit_count(): Returns the number of 1s in the binary representation of x. Can also be interpreted as the minimum number of powers of 2 needed to represent x.

Brain Teasers

2749. Minimum Operations to Make the Integer Zero

Let x = num1 - k * num2, then the problem transforms to: Can x be represented using k powers of 2 (duplicates allowed)?

Find the upper and lower bounds of x and enumerate. Plot x = num1 - k * num2 with k as x-axis and x as y-axis. The answer lies in some points on this line in the first quadrant. Analyze the equation x=2^(i1)+…2^(ik) to find possible x values.

Since the smallest power of 2 is 1, x >= k When x is maximum, k is minimum, i.e. k = x.bit_count()

Enumerate k from small to large, the first satisfying equation is the answer.

3495. Minimum Operations to Make All Array Elements Zero

Dividing a number by 4 and flooring it: binary right shift by two bits For a number with n bits in binary representation, it requires (n+1)//2 operations to become 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def get(x):
    # Calculate the sum of (bit_length + 1)//2 for all numbers from 1 to x
    # e.g. from 16 to 31 (1000 to 1111), all are 4-bit numbers
    # 1=1, 2=10, 3=11, 4=100,5=101,6=110,7=111,8=1110
    base = 1
    cnt = 0
    i = 1  # Start from 1-bit binary numbers
    while base <= x:
        end = min(x, 2*base - 1)
        cnt += (i + 1) // 2 * (end - base + 1)  # bit_length * count of i-bit numbers
        base *= 2
        i += 1
    return cnt