1680. Concatenation of Consecutive Binary 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 109 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1.

Example 2:

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.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 109 + 7, the result is 505379714.

Constraints:

1 <= n <= 10^5

Main Idea of the Problem #

Given an integer n ，please concatenate the binary representations from 1 to n ，and return the result of the decimal number corresponding to the concatenation modulo 10^9 + 7。

Solution Approach #

After understanding the problem statement，first find the pattern of how to concatenate the final binary number。Suppose f(n) is the decimal number after the final transformation。Then according to the problem statement，f(n) = f(n-1) << shift + n this is a recurrence formula。The number of bits shifted left by shift is the length corresponding to the binary representation of n。The value of shift changes as n changes。From the binary carry rule, it can be known that，when it is an integer power of 2，the corresponding binary length will increase by 1 bit。Here bit operations can be used to determine whether it is an integer power of 2。

Another thing that needs to be handled in this problem is the rules of modulo operations。This problem needs to use the addition rule of modulo operations。

Modulo operations are somewhat similar to the basic four arithmetic operations，but division is an exception。
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
a ^ b % p = ((a % p)^b) % p （4）
Associative law：
((a+b) % p + c) % p = (a + (b+c) % p) % p （5）
((a*b) % p * c)% p = (a * (b*c) % p) % p （6）
Commutative law：
(a + b) % p = (b+a) % p （7）
(a * b) % p = (b * a) % p （8）
Distributive law：
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）

This problem needs to use the addition operation rule of modulo operations。

Code #

package leetcode

import (
	"math/bits"
)

// Solution One Simulation
func concatenatedBinary(n int) int {
	res, mod, shift := 0, 1000000007, 0
	for i := 1; i <= n; i++ {
		if (i & (i - 1)) == 0 {
			shift++
		}
		res = ((res << shift) + i) % mod
	}
	return res
}

// Solution Two Bit Operations
func concatenatedBinary1(n int) int {
	res := 0
	for i := 1; i <= n; i++ {
		res = (res<<bits.Len(uint(i)) | i) % (1e9 + 7)
	}
	return res
}