[LeetCode] Beautiful Array

932. Beautiful Array

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
unordered_map<int, vector<int>> dp;
public:
vector<int> beautifulArray(int n) {
if(n == 1) return {1};
if(dp.count(n)) return dp[n];
auto odd = beautifulArray((n + 1) / 2);
auto even = beautifulArray(n/2);
vector<int> res;
for(auto& o : odd) res.push_back(o * 2 - 1);
for(auto& e : even) res.push_back(e * 2);
return dp[n] = res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/07/08/PS/LeetCode/beautiful-array/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.