LC 0932 [M] Beautiful Array - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=O-1ucu8ErEo&ab_channel=HappyCoding

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        def helper(n):
            if n == 1:
                return [1]
            
            odds = helper(n//2 + n%2) # to make the odd number bigger e.g. 3
            evens = helper(n//2) # 2

            # divide and conquer
            # 2*A[k] != A[i] + A[j]
            # even != odd + even
            return [2*x-1 for x in odds] + [2*x for x in evens]

        return helper(n)

        # 001 010 011 100 101 110
        # 1 2 3 4 5
        # 246 135
        # 264 153
        nums = list(range(1, n+1))
        nums.sort(key=lambda x: bin(x)[:1:-1])
        return nums