Hey there! Let's break down why your current solutions are hitting time limits, then fix things with a way more efficient approach.

Why your existing code is timing out #

Both of your solutions work correctly, but their time complexity is too high for large values of A:

• Non-bitwise string approach: Converting every number to a binary string, concatenating them, and counting '1's is really inefficient. Each number's binary representation takes O(log i) time to generate, leading to an overall O(A log A) runtime. Plus, building a massive string for big A eats up memory and slows things down even more.
• Bitwise loop approach: Using i & (i-1) to clear the lowest set bit is smarter than the string method, but it still runs in O(A log A) time. For each number, you loop as many times as there are set bits in it—when A is large (like 1e9), that's way too many iterations.

The efficient mathematical solution #

We can calculate the total set bits in O(log A) time by analyzing each bit position independently. Here's the core logic:
For each bit position k (starting from 0 for the least significant bit):

1. The bit follows a cycle of 2^(k+1) numbers. In each cycle, the bit is set for exactly 2^k consecutive numbers.
2. Calculate how many full cycles fit into A: cycles = A // (2^(k+1)). Multiply this by 2^k to get the count of set bits from complete cycles.
3. For the remaining numbers after the full cycles, count how many have this bit set: it's max(0, remainder - 2^k + 1) (only if the remainder is larger than 2^k—otherwise, there are no extra set bits here).

Code implementation #

def solve(A):
    total_set_bits = 0
    current_bit = 1  # Starts at 2^0 (the least significant bit)
    while current_bit <= A:
        # Calculate full cycles and their contribution
        cycle_count = A // (current_bit * 2)
        total_set_bits += cycle_count * current_bit
        
        # Calculate remaining numbers and their contribution
        remainder = A % (current_bit * 2)
        total_set_bits += max(0, remainder - current_bit + 1)
        
        # Move to the next higher bit position
        current_bit <<= 1
    return total_set_bits

Test with your example (A=3) #

Let's walk through how this works for your sample input:

• Bit position 1 (2^0):
  • Cycle count = 3 // 2 = 1 → adds 1*1 = 1 to the total.
  • Remainder = 3 % 2 =1 → adds max(0,1-1+1)=1. Total is now 2.
• Bit position 2 (2^1):
  • Cycle count =3//4=0 → adds 0.
  • Remainder=3%4=3 → adds max(0,3-2+1)=2. Total becomes 4, which matches your expected result.

This method only loops log2(A) times—even for A=1e9, that's just 30 iterations, so it'll never hit time limits.

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