Today, we will be looking at the following problem:
Given an integer
n, return the decimal value of the binary string formed by concatenating the binary representations of
nin order, modulo
10^9 + 7.
Here is my solution:
In order to figure out this problem, I had to learn about bitwise operations and how shifting bits to the left is equal to multiplying the number by
2 * (number of places shifted).
For example, if I had the number
25 which translates to
11001. A left shift would result in
110010 which is just a zero added to the end. As a result, you will get the number
50 which is also
25 * 2.
Try doing the same with another number, let say
21568 and bit shifting it by 2 places, you will get
21568 * 2 * 2.
Now, we need to know how many places to shift the bits by for each number and that could be figured out by looping through the range of numbers and using the
& — bitwise AND operator. This operator returns
1 only if the bit position of both numbers are
For example, if we had the number
4 in binary which is
3 in binary which is
& operator applied to the 2 numbers would result in
0. This is true for all numbers that correspond with a binary bit position. The decimal representation of a bit position with trailing zeros and the one minus that representation in binary will always yield 0.
As a result, we can loop through all the numbers starting from
1 and when we find a number corresponds with a base 2 bit position with trailing zeros, we add to variable
pow2 which counts the number of times a number has to be bit shifted to make way for the current number to be inserted into the sum.
Before the end of each loop, we shift the results by
Math.pow(2, pow2) and add the current number
i to fill in the zeroes that were added during the bit shifting. A modulo of 10⁹ + 7 is then applied. We apply the modulo during each loop to ensure that the number does not become too big to compute.
And there you have it, the solutions to Leetcode #1680 Concatenation of Consecutive Binary Numbers explained.