1. 문제 소개

Constraints:

• 1 <= n <= 1000

3370. Smallest Number With All Set Bits

2. 나의 풀이법

간단하게 bin()함수를 사용해 이진화했고 그 길이만큼의 1로 이루어진 비트를 다시 정수화했다.
아쉬운 점은 이미 조건을 만족하는 n에 대해서도 알고리즘을 진행한다는 점이며, 시간복잡도가 $O(l)$이라는 점이다.

class Solution:
    def smallestNumber(self, n: int) -> int:
        b = bin(n)[2:]
        l = len(b)
        ans = 0
        for i in range(l):
            ans += 2 ** i
        return ans

3. 다른 풀이법

Editorial의 풀이는 시간복잡도가 $O(log\,n)$이다.

class Solution:
    def smallestNumber(self, n: int) -> int:
        x = 1
        while x < n:
            x = x * 2 + 1
        return x

4. 결론

쉬운 문제였는데 특이한 점은 23ms가 걸린 코드였다.
n부터 3n까지 하나하나 이진화하고 검사하는데, 이렇게 생각하는 방법도 있구나 하는 생각이 든다.

class Solution:
    def smallestNumber(self, n: int) -> int:
        for i in range(n, n*3):
            a = format(i, 'b')
            if a.count('0') == 0:
                return i
            else:
                continue