We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Beautiful Array

Number: 968

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon, Google

Problem Description

Given an integer n, return any beautiful array of length n. A beautiful array is a permutation of the integers in the range [1, n] such that for any indices i < k < j, 2 * nums[k] is not equal to nums[i] + nums[j].

Key Insights

  • The solution employs a divide and conquer strategy.
  • Recursively construct a beautiful array for a smaller size.
  • Transform the smaller array into two parts: one for odd numbers (mapping x to 2x - 1) and one for even numbers (mapping x to 2x).
  • Concatenating these parts ensures that the arithmetic condition is maintained.

Space and Time Complexity

Time Complexity: O(n log n) due to the recursive division of the problem and linear work at each level. Space Complexity: O(n) for storing the array and the recursion call stack.

Solution

We solve the problem using recursion with a divide and conquer approach. The key is to observe that if we have a beautiful array for a smaller size, we can construct a beautiful array for a larger size by applying a transformation:

  1. For each number x in the beautiful array of size k = (n+1)/2, transform it to 2*x - 1 to fill the odd positions.
  2. For each number x in the beautiful array of size n/2, transform it to 2*x to fill the even positions. Concatenating these two lists yields a beautiful array for n. This transformation maintains the property that no element is the arithmetic mean of two other elements.

Code Solutions

def beautifulArray(n):
    # Base case: when n is 1, return list with a single element.
    if n == 1:
        return [1]
    # Recursively build the beautiful array by generating odd and even parts.
    odds = [2 * x - 1 for x in beautifulArray((n + 1) // 2)]
    evens = [2 * x for x in beautifulArray(n // 2)]
    return odds + evens

# Example usage:
result = beautifulArray(5)
print(result)  # Outputs a beautiful array of length 5
← Back to All Questions