Algorithm
Problem Name: 932. Beautiful Array
An array nums of length n is beautiful if:
numsis a permutation of the integers in the range[1, n].- For every
0 <= i < j < n, there is no indexkwithi < k < jwhere2 * 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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> beautifulArray(int N) {
vector<int> res;
for (int i = 1; i < = N; ++i) {
res.push_back(i);
}
return beautify(res);
}
vector<int> beautify(vector<int>& v) {
if (v.size() == 1) {
return v;
}
vector<int> odd, even;
for (int i = 0; i < v.size(); ++i) {
if (i % 2) {
odd.push_back(v[i]);
} else {
even.push_back(v[i]);
}
}
auto L = beautify(odd);
auto R = beautify(even);
for (const auto& x: R) {
L.push_back(x);
}
return L;
}
};
Input
n = 4
Output
[2,1,4,3]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const beautifulArray = function(N) {
let res = [];
res.push(1);
while (res.length < N) {
const tmp = [];
for (let i of res) if (i * 2 - 1 <= N) tmp.push(i * 2 - 1);
for (let i of res) if (i * 2 < = N) tmp.push(i * 2);
res = tmp;
}
return res;
};
Input
n = 4
Output
[2,1,4,3]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def beautifulArray(self, N):
if N == 1: return [1]
half = self.beautifulArray(N - N // 2)
return [i * 2 - 1 for i in half] + [i * 2 for i in half if i * 2 <= N]
Input
n = 5
Output
[3,1,2,5,4]