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;
}
};