[LeetCode] 1680. Concatenation of Consecutive Binary Numbers

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

---

문제 풀이

• 숫자 크기에 따라 이진수 값들을 연속으로 붙여준다.
• 붙여서 만든 이진수 값을 십진수 값으로 변환한다. 
• n의 제한값은 10^5 이기 때문에 N^2 알고리즘은 불가하다.
• 1부터 n까지의 숫자를 이진수로 변환하고 파이썬에서는 0b가 붙기 때문에, 그 부분을 제거 하고 더해준다. 
• 이진수를 십진수로 바꾸고 10**9 + 7 값으로 모듈러 계산을 해준 후 리턴한다.
• PS: 시간복잡도는 NlogN, 이진수로 변환할때 lonN의 시간이 추가된다.

소스 코드

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        result = ''
        for i in range(1, n+1):
            result += bin(i)[2:]
        return int(result,2) % (10**9 + 7)