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<>();
        result.add(1);
        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();
    }
}