0932-beautiful-array

Try it on leetcode

Description

An array nums of length n is beautiful if:

• nums is a permutation of the integers in the range [1, n].
• For every 0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].

Given the integer n, return any beautiful array nums of length n. There will be at least one valid answer for the given n.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= n <= 1000

Solution(Python)

from functools import lru_cache


class Solution:
    def beautifulArray(self, N):
        @lru_cache
        def f(N): # 2
            if N <= 1:
                return [1]
            odds = f((N+1)//2) # 
            evens = f(N//2)
            ans = [2*x-1 for x in odds] + [2*x for x in evens]
            return ans
        return f(N)