Beautiful Array Problem


Description

LeetCode Problem 932.

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:

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

Example 2:

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

Constraints:

  • 1 <= n <= 1000


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> beautifulArray(int N) {
        if (N == 1) return {1};
        vector<int> even = beautifulArray(N / 2);
        vector<int> odd = beautifulArray(N - N / 2);
        vector<int> rtn;
        for (int x : even) 
            rtn.push_back(x * 2);
        for (int x : odd) 
            rtn.push_back(x * 2 - 1);
        return rtn;
    }
};




Related Posts

Three Equal Parts Problem

LeetCode 927. You are given an array arr which consists...

Surface Area Of 3D Shapes Problem

LeetCode 892. You are given an n x n grid...

Super Palindromes Problem

LeetCode 906. Let’s say a positive integer is a super-palindrome...

Smallest Range I Problem

LeetCode 908. You are given an integer array nums and...

Projection Area Of 3D Shapes Problem

LeetCode 883. You are given an n x n grid...

Prime Palindrome Problem

LeetCode 866. Given an integer n, return the smallest prime...