For some fixed N, an array A is beautiful if it is a permutation of the integers 1, 2, ..., N, such that:
For every i < j, there is no k with i < k < j such that A[k] * 2 = A[i] + A[j].
Given N, return any beautiful array A.  (It is guaranteed that one exists.)
 
Example 1:
Input: 4
Output: [2,1,4,3]


Example 2:
Input: 5
Output: [3,1,2,5,4]
 

Note:

1 <= N <= 1000

Difficulty: interview

Starter code:

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        

Solutions:
class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        res = [1]
        
        while len(res) < N:
            res = [i*2-1 for i in res]+ [i*2 for i in res]
            
        return [i for i in res if i <= N]

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        nums = list(range(1, N+1))
        
        def helper(nums):
            if len(nums) < 3:
                return nums
            odd = nums[::2]
            even = nums[1::2]
            return helper(even) + helper(odd)
        return helper(nums)  


class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        result = list(range(1, N + 1))
        def partition(i, j):
            if j - i <= 2: return
            result[i:j] = result[i:j:2] + result[i + 1:j:2]
            m = i + (j - i + 1) // 2
            partition(i, m)
            partition(m, j)
        
        partition(0, N)
        return result


class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        def find_array(N: int, dic = defaultdict(list)) -> List[int]:
            if dic[N]:
                pass
            elif N == 1:
                dic[1] = [1]
            else:
                even_N = N // 2
                odd_N = N - even_N
                odd_temp = find_array(odd_N)
                even_temp = find_array(even_N)
                odd_temp = [2*i - 1 for i in odd_temp]
                even_temp = [2*i for i in even_temp]
                dic[N] = odd_temp + even_temp
            return dic[N]
        return find_array(N)

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        r=[1]
        while(len(r)<N):
            o=[2*i-1 for i in r]
            e=[2*(i) for i in r]
            r=o+e
        ans=[]
        for i in range(len(r)):
            if(r[i]<=N):
                ans.append(r[i])
        return ans
        


class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        
        res = [1]
        
        while len(res) < N:
            tmp = []
            for num in res:
                if num * 2 - 1 <= N:
                    tmp.append(num * 2 - 1)
            for num in res:
                if num * 2 <= N:
                    tmp.append(num * 2)
            res = tmp
        
        return res

#https://www.cnblogs.com/grandyang/p/12287146.html
class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        lst = [1]
        while len(lst)<N:
            tmp1 = [2*i-1 for i in lst ]
            tmp2 = [2*i for i in lst]
            tmp1.extend(tmp2)
            lst = [i for i in tmp1 if i<=N]
            # print (lst)
        return lst


class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        nums=[]
        for i in range(1,N+1):
            nums.append(i)
        def div(nums):
            if len(nums)<3:
                return nums
            odd=nums[1::2]
            even=nums[::2]
            return div(even)+div(odd)
        return div(nums)


class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        answers = []
        
        queue = [list(range(1, N + 1))]
        while queue:
            ls = queue.pop()
            if len(ls) > 2:
                odd = []
                even = []
                
                for i, val in enumerate(ls):
                    if i % 2:
                        odd.append(val)
                    else:
                        even.append(val)
                
                queue.append(odd)
                queue.append(even)
            else:
                answers += ls
        
        return answers

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        return [i for i in [int('{:010b}'.format(i)[::-1], 2) for i in range(1, 1 << 10)] if i <= N]


class Solution:
    
    def beautifulArray(self, N: int) -> List[int]:
        self.N = N
        self.rst = []
        counter = 0
        while N > 0:
            N = N >> 1
            counter += 1
        self.tree = [0] * (2**(counter+1))
#        print(len(self.tree))
        self.tree[0] = 1
        self.buildtree(0, 0)
        self.traverse(0)
        return self.rst
        
    def traverse(self, i):
        if 2*i + 1 > len(self.tree) or self.tree[2*i + 1] == 0:
            self.rst.append(self.tree[i])
        else:
            self.traverse(2*i+1)
            self.traverse(2*i + 2)
        
    def buildtree(self, i, level):
        if self.tree[i] + 2 ** level <= self.N:
            self.tree[2*i + 1] = self.tree[i]
            self.tree[2*i + 2] = self.tree[i] + 2**level
            self.buildtree(2*i + 1, level + 1)
            self.buildtree(2*i + 2, level + 1)

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        res = [1]
        while len(res) < N:
            res = [i * 2 - 1 for i in res] + [i * 2 for i in res]
        return [i for i in res if i <= N]