[Leetcode] 1680. Concatenation of Consecutive Binary Numbers

문제 : 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)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1680.%20Concatenation%20of%20Consecutive%20Binary%20Numbers.cpp