솔루션: 연속 이진수의 연결

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.

Leetcode 문제 #1680(중간): 연속 이진수의 연결

설명:

정수 n 가 주어지면 1 의 이진 표현을 n 순서대로 모듈로 10^9 + 7 로 연결하여 형성된 이진 문자열의 10진수 값을 반환합니다.


예:


예 1:



입력:
n = 1

산출:
1

설명:
이진수의 "1"은 십진수 값 1에 해당합니다.



예 2:



입력:
n = 3

산출:
27

설명:
2진법에서 1, 2, 3은 "1", "10", "11"에 해당합니다. 이들을 연결하면 십진법 값 27에 해당하는 "11011"이 됩니다.



예 3:



입력:
n = 12

산출:
505379714

설명:
연결 결과 "1101110010111011110001001101010111100"이 됩니다. 그 십진수 값은 118505380540입니다. 모듈로 109 + 7 이후의 결과는 505379714입니다.


제약 조건:

1 <= n <= 10^5

아이디어:

숫자를 문자열로 변환하거나 매번 이진 길이를 계산하는 것과 관련된 덜 효율적인 솔루션이 있지만 가장 효율적인 솔루션은 실제로 훨씬 더 기본적입니다. 왜냐하면 이진수가 길이를 1만큼 늘릴 때를 정확히 알고 있기 때문입니다.

그래서 우리는 i를 새로운 ans에 맞추기 위해 ans를 얼마나 곱해야 하는지 추적하기 위해 len을 사용하는 동안 반복할 수 있습니다. 1e9+7로 모드를 변경하는 것을 잊지 마십시오.


자바스크립트 코드:

var concatenatedBinary = function(n) {
    let ans = 1, len = 0b100
    for (let i = 2; i <= n; i++) {
        if (i === len) len <<= 1
        ans = (ans * len + i) % 1000000007
    }
    return ans
};

동일한 코드이지만 len에 대해 이진수 대신 십진수를 사용합니다.

var concatenatedBinary = function(n) {
    let ans = 1, len = 4
    for (let i = 2; i <= n; i++) {
        if (i === len) len *= 2
        ans = (ans * len + i) % 1000000007
    }
    return ans
};