Skip to content

1680. Concatenation of Consecutive Binary Numbers

Description

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

Solutions

Solution 1: Bit Manipulation

By observing the pattern of number concatenation, we can find that when concatenating to the \(i\)-th number, the result \(ans\) formed by concatenating the previous \(i-1\) numbers is actually shifted to the left by a certain number of bits, and then \(i\) is added. The number of bits shifted is the number of binary digits in \(i\).

The time complexity is \(O(n)\), where \(n\) is the given integer. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        ans = 0
        for i in range(1, n + 1):
            ans = (ans << i.bit_length() | i) % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int concatenatedBinary(int n) {
        final int mod = (int) 1e9 + 7;
        long ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans = (ans << (32 - Integer.numberOfLeadingZeros(i)) | i) % mod;
        }
        return (int) ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int concatenatedBinary(int n) {
        const int mod = 1e9 + 7;
        long long ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans = (ans << (32 - __builtin_clz(i)) | i) % mod;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
func concatenatedBinary(n int) (ans int) {
    const mod = 1e9 + 7
    for i := 1; i <= n; i++ {
        ans = (ans<<bits.Len(uint(i)) | i) % mod
    }
    return
}

1
2
3
4
5
6
7
8
function concatenatedBinary(n: number): number {
    const mod = 1_000_000_007;
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        ans = (((ans * (1 << (32 - Math.clz32(i)))) % mod) + i) % mod;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn concatenated_binary(n: i32) -> i32 {
        let mod_: i64 = 1_000_000_007;
        let mut ans: i64 = 0;
        for i in 1..=n as i64 {
            let bit_length: u32 = 64 - i.leading_zeros() as u32;
            ans = ((ans << bit_length) | i) % mod_;
        }
        ans as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 * @param {number} n
 * @return {number}
 */
var concatenatedBinary = function (n) {
    const mod = 1_000_000_007;
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        ans = (((ans * (1 << (32 - Math.clz32(i)))) % mod) + i) % mod;
    }
    return ans;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Solution {
    public int ConcatenatedBinary(int n) {
        const int mod = 1000000007;
        long ans = 0;
        for (int i = 1; i <= n; ++i) {
            int bitLength = 32 - System.Numerics.BitOperations.LeadingZeroCount((uint)i);
            ans = ((ans << bitLength) | i) % mod;
        }
        return (int)ans;
    }
}

Solution 2: Bit Manipulation (Optimization)

In Solution 1, we need to calculate the number of binary digits of \(i\) each time, which adds some extra computation. We can use a variable \(\textit{shift}\) to record the current number of bits to shift. When \(i\) is a power of \(2\), \(\textit{shift}\) needs to be incremented by \(1\).

The time complexity is \(O(n)\), where \(n\) is the given integer. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int concatenatedBinary(int n) {
        const int mod = 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 ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function concatenatedBinary(n: number): number {
    const mod = 1_000_000_007;
    let ans = 0;
    let shift = 0;
    for (let i = 1; i <= n; i++) {
        if ((i & (i - 1)) === 0) {
            shift++;
        }
        ans = (((ans * (1 << shift)) % mod) + i) % mod;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn concatenated_binary(n: i32) -> i32 {
        let mod_: i64 = 1_000_000_007;
        let mut ans: i64 = 0;
        let mut shift: u32 = 0;
        for i in 1..=n as i64 {
            if (i & (i - 1)) == 0 {
                shift += 1;
            }
            ans = ((ans << shift) | i) % mod_;
        }
        ans as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {number} n
 * @return {number}
 */
var concatenatedBinary = function (n) {
    const mod = 1_000_000_007;
    let ans = 0;
    let shift = 0;
    for (let i = 1; i <= n; i++) {
        if ((i & (i - 1)) === 0) {
            shift++;
        }
        ans = (((ans * (1 << shift)) % mod) + i) % mod;
    }
    return ans;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class Solution {
    public int ConcatenatedBinary(int n) {
        const int mod = 1000000007;
        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;
    }
}

Comments