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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Mathematics

Divide and conquer

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


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]
		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)
		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)