[LeetCode] Concatenation of Consecutive Numbers

Problem: Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10^9 + 7.

Example:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11". After concatenating them, we have "11011", which corresponds to the decimal value 27.

Approach: We are going to use the approach which we took in our previous problem of Concatenating binary representation of two numbers. Let's take an example say n = 3 to understand the approach. 

n = 1 then answer is obviously 1

n = 2  what we will do is we will left shift answer by number of bits in 2 and add 2 in the answer so answer will be 1 * 2 ^ 2 + 2 = 6

n = 3, 6 * 2^2 + 3 = 27

answer = previous_answer * 2 ^ (num_of_bits_in_current_number) + current_number 

This is the core logic obviously we need to take modulo of 10^9 + 7 which is given to avoid overflow. 

That's all!

Implementation in C#:

        public int ConcatenatedBinary(int n)

        {

            ulong result = 0;

            ulong modValue = 1000000007;

            int numOfBits = 1;            

            for (ulong i = 1; i <= (ulong)n; ++i)

            {

                result = (((result << numOfBits) % modValue) + i) % modValue;

                if ((i & (i + 1)) == 0)

                {

                    ++numOfBits;

                }

            }

            return (int)result;

        }

Complexity: O(n)