1680. Concatenation of Consecutive Binary Numbers

Time: O(n log n)

Space: O(1)

Intuition

Concatenate binary representations of 1,2,...,n. Find k-th bit. Work out length = sum(floor(log2(i))+1 for i in 1..n) and binary search.

Algorithm

1Total length grows. Binary search for which number contains the k-th bit.
2Determine bit position within that number.

Common Pitfalls

•Total bit length = sum of bit lengths. Find the number containing position k using prefix sums.

1680.cs

// Approach: Shift accumulated result left by bit-length of i, then OR with i, all mod 1e9+7.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int ConcatenatedBinary(int n)
    {
        const int MOD = 1_000_000_007;
        long ans = 0;
        int numberOfBits = 0;

        for (int i = 1; i <= n; ++i)
        {
            if (BitOperations.PopCount((uint)i) == 1)
                ++numberOfBits;
            ans = ((ans << numberOfBits) % MOD + i) % MOD;
        }

        return (int)ans;
    }
}

Was this solution helpful?