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

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

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

Key: Suppose an array is already a beautiful array, e.g. [1,3,2], then linear transformation of it, e.g. +, or * on each element would not kill beautiful property;

  1. [1,3,2] + 1 = [2,4,3], still beautiful;
  2. [1,3,2] * 2 = [2,6,4], still beautiful.

As a result, if an array A satisfies beautiful property, i*2-1 would create all-odd element beautiful array based on A, i*2 would create an all-even element beautiful array. Merge them, and result array is still beautiful, because left & right part is beautiful and two numbers from each part would generate a odd sum whose half is x.5—definitely not an element in array.

iteration:

1
2
3
4
5
6
class Solution(object):
    def beautifulArray(self, N):
        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]

recursion:

1
2
3
4
5
6
class Solution(object):
    def beautifulArray(self, N):
        if N == 1 : return [1] # terminal condition 
        odd = [i * 2 - 1 for i in self.beautifulArray(N/2 + N%2)]
        even = [i * 2 for i in self.beautifulArray(N/2)]
        return odd + even

In recursion, if:RuntimeError: maximum recursion depth exceeded, usually it’s because terminal condition was left unattended.

In recursion, always 2 return:

  1. terminal condition
  2. divide and conquer going down call stack, return going up