Forem

Ruairí O'Brien
Ruairí O'Brien

Posted on

Day 27 - Concatenation of Consecutive Binary Numbers

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

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay