[알고리즘 ] Concatenation of Consecutive Binary Numbers

포인트

1. 파이썬은 진법 변환이 엄청 편하며 long long 구별 필요 없이 int 를 사용하면 된다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

class Solution {
public:
    int concatenatedBinary(int n) {
        long res = 0, mod = 1e9+7, len_of_curr = 0;
        for (int i = 1; i <= n; i++) {
		
			// the len increases every time we reach a number which is a power of two.
            if ((i & (i-1)) == 0)
                len_of_curr++;
				
            res = (res << len_of_curr) % mod;
            res += i % mod;
        }
        return res;
    }
};

python

def d_to_b(n):
    return bin(n).replace('0b', '')

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        result=''
        for i in range(1, n+1):
            result+=d_to_b(i)
        #11011~~~~
        
        modulo = 10**9+7
        return int(result, 2) % modulo