알고리즘 문제/Leetcode
[Leetcode] 1680. Concatenation of Consecutive Binary Numbers
햄과함께
2022. 9. 24. 16:53
320x100
문제 : https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/
숫자 n의 2진법 자리 수는 log2(n) + 1이다.
1부터 n까지 탐색하면서 이때까지의 합계를 sum이라 하자.
예를 들어, 숫자 5의 숫자 sum의 이진법 뒤에 추가한다고 하면
숫자 5의 이진법은 101. 자리수는 3이다.
따라서 sum을 앞으로 세 칸 움직이고 (<<3) 101을 추가해준다.
그럼 이렇게 만들어진 수의 합은 (sum << 3) + 5가 될 것이다.
Sum(n+1) = (Sum(n) << (log2(n) + 1)) + n점화식으로 하면 위와 같다.
여기에 모듈러 연산을 적절히 추가한다.
시간복잡도는 O(n)
320x100