DEV Community

loading...

Day 27 - Concatenation of Consecutive Binary Numbers

ruarfff profile image Ruairí O'Brien ・1 min read

The 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 1:

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

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.
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

Constraints:

  • 1 <= n <= 105

Tests

import pytest
from .Day27_ConcatenationOfConsecutiveBinaryNumbers import Solution

s = Solution()


@pytest.mark.parametrize(
    "n,expected",
    [
        (1, 1),
        (3, 27),
        (12, 505379714),
    ],
)
def test_concatenated_binary(n, expected):
    assert s.concatenatedBinary(n) == expected
Enter fullscreen mode Exit fullscreen mode

Solution

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        l = 0
        ans = 0
        for i in range(1, n + 1):            
            if i & (i - 1) == 0:
                l += 1
            ans = ((ans << l) | i) % (10 ** 9 + 7)
        return ans
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Discussion (0)

pic
Editor guide