Solution Explanation

This problem asks to construct a "beautiful array" of length n, where the array is a permutation of numbers from 1 to n, and for any three indices i < k < j, 2 * nums[k] is not equal to nums[i] + nums[j]. The solution uses a divide-and-conquer approach.

Approach:

The core idea is based on the observation that if you have a beautiful array A, you can construct a larger beautiful array by multiplying all elements of A by 2 and subtracting 1 from all elements of A, then concatenating the results.

1. Base Case: If n is 1, the beautiful array is simply [1].

2. Recursive Step:

   • Recursively construct a beautiful array left for (n + 1) // 2 elements.
   • Recursively construct a beautiful array right for n // 2 elements.
   • Create a new array ans by multiplying each element in left by 2 and subtracting 1 (2 * x - 1), and multiplying each element in right by 2 (2 * x).
   • Concatenate left and right to form the final ans.

This recursive construction guarantees the "beautiful" property. The multiplication and subtraction steps ensure that the sum of any two elements will not be double any element in between.

Time Complexity Analysis:

The time complexity is dominated by the recursive calls. At each level of recursion, the problem size is roughly halved. This leads to a logarithmic number of recursive calls. The work done at each level is linear in the size of the subarray. Therefore, the overall time complexity is O(n log n).

Space Complexity Analysis:

The space complexity is also O(n log n) due to the recursive calls. Each level of recursion creates new arrays of size roughly half the size of the previous level. The total space used by all these arrays will be proportional to n log n. In practice, because of tail recursion optimization (or iterative implementation), this could be reduced to O(n).

Code Explanation (Python):

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        if n == 1:
            return [1]
        left = self.beautifulArray((n + 1) >> 1)  #Right bit shift is equivalent to integer division by 2
        right = self.beautifulArray(n >> 1)
        left = [x * 2 - 1 for x in left]         #Transform left array
        right = [x * 2 for x in right]           #Transform right array
        return left + right                      #Concatenate and return

The code directly implements the recursive approach described above. The >> operator performs a right bit shift, which is a faster way to perform integer division by 2. List comprehensions are used for efficient transformation of the left and right arrays. The + operator efficiently concatenates the two lists.

The Java, C++, and Go code follow the same logic, with only minor syntax differences. All have the same time and space complexity characteristics.