Welcome to Subscribe On Youtube

932. Beautiful Array

Description

An array nums of length n is beautiful if:

• nums is a permutation of the integers in the range [1, n].
• For every 0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].

Given the integer n, return any beautiful array nums of length n. There will be at least one valid answer for the given n.

 

Example 1:

Input: n = 4
Output: [2,1,4,3]

Example 2:

Input: n = 5
Output: [3,1,2,5,4]

 

Constraints:

• 1 <= n <= 1000

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public int[] beautifulArray(int n) {
          if (n == 1) {
              return new int[] {1};
          }
          int[] left = beautifulArray((n + 1) >> 1);
          int[] right = beautifulArray(n >> 1);
          int[] ans = new int[n];
          int i = 0;
          for (int x : left) {
              ans[i++] = x * 2 - 1;
          }
          for (int x : right) {
              ans[i++] = x * 2;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      vector<int> beautifulArray(int n) {
          if (n == 1) return {1};
          vector<int> left = beautifulArray((n + 1) >> 1);
          vector<int> right = beautifulArray(n >> 1);
          vector<int> ans(n);
          int i = 0;
          for (int& x : left) ans[i++] = x * 2 - 1;
          for (int& x : right) ans[i++] = x * 2;
          return ans;
      }
  };
  

• class Solution:
      def beautifulArray(self, n: int) -> List[int]:
          if n == 1:
              return [1]
          left = self.beautifulArray((n + 1) >> 1)
          right = self.beautifulArray(n >> 1)
          left = [x * 2 - 1 for x in left]
          right = [x * 2 for x in right]
          return left + right
  
  

• func beautifulArray(n int) []int {
  	if n == 1 {
  		return []int{1}
  	}
  	left := beautifulArray((n + 1) >> 1)
  	right := beautifulArray(n >> 1)
  	var ans []int
  	for _, x := range left {
  		ans = append(ans, x*2-1)
  	}
  	for _, x := range right {
  		ans = append(ans, x*2)
  	}
  	return ans
  }
  

All Problems

All Solutions