# Solution For Beautiful Array

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.

## Step by Step Implementation For Beautiful Array

```class Solution {
public int[] beautifulArray(int N) {
List result = new ArrayList<>();
while (result.size() < N) {
List tmp = new ArrayList<>();
for (int i : result) if (i * 2 - 1 <= N) tmp.add(i * 2 - 1);
for (int i : result) if (i * 2 <= N) tmp.add(i * 2);
result = tmp;
}
return result.stream().mapToInt(i->i).toArray();
}
}```
```def beautifulArray(N):
# Base case: if N = 1, then the array is already beautiful
if N == 1:
return [1]

# Step 1: Get the first beautiful array of size N/2
A = beautifulArray(N/2)

# Step 2: Get the second beautiful array of size N/2
B = beautifulArray(N/2)

# Step 3: Combine the two arrays into one array
# We do this by concatenating A and B,
# then inserting all elements of B into A at even indices
C = A + B
for i in range(0, len(B)):
C.insert(2*i, B[i])

# Step 4: Return the combined array
return C```
```var beautifulArray = function(N) {
// create an empty array to store the beautiful array
var res = [];

// base case: if N is 1, return [1]
if (N === 1) return [1];

// recursive case:
// 1. get the beautiful array for N - 1
// 2. create two subarrays: one with odd indices of the previous array,
//    and one with even indices of the previous array
// 3. concatenate the two subarrays together in the following order:
//    odd subarray + even subarray + 1
var prev = beautifulArray(N - 1);
var odd = prev.filter((num, index) => index % 2 === 1);
var even = prev.filter((num, index) => index % 2 === 0);
return [...odd, ...even, N];
};```
```class Solution {
public:
vector beautifulArray(int N) {
if (N == 1) return {1};
vector ans = beautifulArray((N+1)/2);
for (int &x: ans) x *= 2;
for (int i = 0; i < N/2; ++i) ans.push_back(ans[i]*2-1);
return ans;
}
};

/*

This is a recursive solution to the problem.

The idea is to start with an array of size 1 containing only the number 1.

Then, we recursively generate the array of size N by doing the following:

1. Generate the array of size (N+1)/2

2. Multiply each element of the array by 2

3. Add the numbers 1, 3, 5, ..., 2*N-1 to the end of the array

4. Return the resulting array```
```public class Solution {
public int[] BeautifulArray(int N) {
List res = new List() {1};
while (res.Count < N) {
List temp = new List();
foreach (int i in res) {
if (i * 2 - 1 <= N) temp.Add(i * 2 - 1);
}
foreach (int i in res) {
if (i * 2 <= N) temp.Add(i * 2);
}
res = temp;
}
return res.ToArray();
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]