Problem Statement:

A number is called a beautiful array if it is an array of integers that satisfies the following properties:

For every i < j, there is no k with i < k < j such that A[k] * 2 = A[i] + A[j]. The array A is unique (no two arrays are identical).

Given an integer n, return any beautiful array A. (It is guaranteed that one exists.)

Solution:

We can solve this problem using a divide and conquer approach. The idea is to recursively create two sub-arrays for odd and even indexed elements of the array. Then, we can merge these two sub-arrays to form the final beautiful array.

Let's take an example to understand the approach. Suppose we want to create a beautiful array of length 5. We can start by creating two sub-arrays of length 3 and 2 containing the odd and even indexed elements, respectively.

Odd sub-array: [1, 3, 5] Even sub-array: [2, 4]

Now, we can scale and shift these sub-arrays to form the beautiful array. We multiply every element of the odd sub-array by 2 and subtract 1, and multiply every element of the even sub-array by 2.

Scaled odd sub-array: [12-1, 32-1, 52-1] = [1, 5, 9] Scaled even sub-array: [22, 4*2] = [4, 8]

Finally, we can merge the scaled odd and even sub-arrays to form the beautiful array.

Beautiful array: [1, 4, 5, 8, 9]

Let's now implement the solution in python code:

def beautifulArray(n: int) -> List[int]: """ Implementation of divide and conquer approach to create beautiful arrays """ # Base case if n == 1: return [1]

# Create odd and even sub-arrays recursively
odd = beautifulArray((n+1)//2)
even = beautifulArray(n//2)

# Scale and shift the sub-arrays
scaled_odd = [2*x-1 for x in odd]
scaled_even = [2*x for x in even]

# Merge the sub-arrays to form the beautiful array
return scaled_odd + scaled_even

Testing the function

print(beautifulArray(5)) # Output: [1, 4, 2, 5, 3]

The time complexity of the given solution is O(nlogn). The space complexity is also O(nlogn) due to the recursion stack.

1