Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1680.html
1680. Concatenation of Consecutive Binary Numbers (Medium)
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 <= 105
Related Topics:
Math
Solution 1.
Let f(n)
be the answer. sum_len(a, b) = sum( len(i) | a <= i <= b)
and len(i)
is the number of bits in i
.
For example: len(1) = 1
, len(3) = 2
, len(6) = 3
. sum_len(1,4) = len(1) + len(2) + len(3) + len(4) = 1 + 2 + 2 + 3 = 8
.
So we have
f(n) = (1 << sum_len(2, n)) + (2 << sum_len(3, n)) + ... + ((n - 1) << sum_len(n, n)) + (n << 0)
// Example: f(4) = 11011100 = (1 << (2+2+3)) + (2 << (2+3)) + (3 << 3) +(4 << 0)
f(n-1) = (1 << sum_len(2, n-1)) + (2 << sum_len(3, n-1)) + ... + ((n - 1) << 0)
f(n) = (f(n-1) << len(n)) + n
Since f(0) = 0
, we can iteratively build f(n)
.
f(0) = 0
f(1) = 1 = (f(0) << 1) + 1 // len(1) = 1
f(2) = 110 = (f(1) << 2) + 2 // len(2) = 2
f(3) = 11011 = (f(2) << 2) + 3 // len(3) = 2
...
// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int concatenatedBinary(int n) {
long ans = 0, mod = 1e9+7;
for (int i = 1; i <= n; ++i) {
int len = 0;
for (int j = i; j; j >>= 1, ++len);
ans = ((ans << len) % mod + i) % mod;
}
return ans;
}
};
Solution 2.
We spent O(logN)
time for calculating the len
. We can reduce it to O(1)
with the help of __builtin_clz
which returns the number of leading zeros for a number, so len = 32 - __builtin_clz(i)
.
// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int concatenatedBinary(int n) {
long ans = 0, mod = 1e9+7;
for (int i = 1; i <= n; ++i) ans = ((ans << (32 - __builtin_clz(i))) % mod + i) % mod;
return ans;
}
};
Or, with the observation that the len
only increment when the i
is a power of 2
, we can increment len
only when i
has a single bit 1
. We can check this via (i & (i - 1)) == 0
or __builtin_popcount(i) == 1
.
// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int concatenatedBinary(int n) {
long ans = 0, mod = 1e9+7, len = 0;
for (int i = 1; i <= n; ++i) {
if ((i & (i - 1)) == 0) ++len;
ans = ((ans << len) % mod + i) % mod;
}
return ans;
}
};
-
class Solution { public int concatenatedBinary(int n) { final int MODULO = 1000000007; long num = 0; int bits = 0; for (int i = 1; i <= n; i++) { if ((i & (i - 1)) == 0) bits++; num = ((num << bits) + i) % MODULO; } return (int) num; } } ############ class Solution { public int concatenatedBinary(int n) { final int mod = (int) 1e9 + 7; long ans = 0; int shift = 0; for (int i = 1; i <= n; ++i) { if ((i & (i - 1)) == 0) { ++shift; } ans = (ans << shift | i) % mod; } return (int) ans; } }
-
// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/ // Time: O(NlogN) // Space: O(1) class Solution { public: int concatenatedBinary(int n) { long ans = 0, mod = 1e9+7; for (int i = 1; i <= n; ++i) { int len = 0; for (int j = i; j; j >>= 1, ++len); ans = ((ans << len) % mod + i) % mod; } return ans; } };
-
class Solution: def concatenatedBinary(self, n: int) -> int: mod = 10**9 + 7 ans = shift = 0 for i in range(1, n + 1): if (i & (i - 1)) == 0: shift += 1 ans = (ans << shift | i) % mod return ans ############ # 1680. Concatenation of Consecutive Binary Numbers # https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/ class Solution: def concatenatedBinary(self, n: int) -> int: M = 10 ** 9 + 7 s = [] for i in range(1, n+1): s.append(str(bin(i)[2:])) s = "".join(s) return int(s,2) % M
-
func concatenatedBinary(n int) (ans int) { const mod = 1e9 + 7 shift := 0 for i := 1; i <= n; i++ { if i&(i-1) == 0 { shift++ } ans = (ans<<shift | i) % mod } return }
-
function concatenatedBinary(n: number): number { const mod = BigInt(10 ** 9 + 7); let ans = 0n; let shift = 0n; for (let i = 1n; i <= n; ++i) { if ((i & (i - 1n)) == 0n) { ++shift; } ans = ((ans << shift) | i) % mod; } return Number(ans); }