# [LeetCode 932. Beautiful Array ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/611/week-4-july-22nd-july-28th/3829/)
### Daily challenge Jul 28, 2021 (MEDIAN)

>For some fixed n, an array `nums` is beautiful if it is a permutation of the integers `1, 2, ..., n`, such that:
>
>For every `i < j`, there is **no** `k` with `i < k < j` such that **`nums[k] * 2 = nums[i] + nums[j]`**.
>
>Given `n`, return **any** beautiful array nums. (It is guaranteed that one exists.)

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

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

:::warning
**Constraints:**
* 1 <= n <= 1000
:::

---

### Approach 1 : Devide and Conquer :book:
**`4 ms ( 73.27% )`** **`O(N)`**

:::success
**`Beautiful array`** 規則 **`nums[k] * 2 = nums[i] + nums[j]`**， **`i <= k <= j`**。
目標將 `array` 分成 **odd + even** 兩部分。
因為 `nums[k] * 2` 必為**偶數**，所以 `nums[i]、nums[j]`如果是**一奇一偶**，必定符合。
:::

假設 `arr` 是 `Beautiful Array`，
我們可以透過兩個運算性質保證之後建立的陣列同樣也是 `Beautiful Array`。
>假設 **`A[k] * 2 != A[i] + A[j]`**。
>1. 加法 :
>> **`(A[k] + x) * 2 = A[k] * 2 + 2x`**。
>> ---> **`A[k] * 2 + 2x != (A[i] + x) + (A[j] + x)`**。
>2. 乘法 :
>> **`(A[k] * x) * 2 = A[k] * 2x`**。
>> ---> **`A[k] * 2x != (A[i] * x) + (A[j] * x)`**。

---

>EXAMPLE : **N = 7**
>* Initial ---> **`arr = [1]`**。
>* `odd = [1]`、`even = [2]`。
>---> **`arr = odd + even = [1, 2]`**。
>* `odd = [1, 3]`、`even = [2, 4]`。
>---> **`arr = [1, 3, 2, 4]`**。
>* `odd = [1, 5, 3, 7]`、`even = [2, 6, 4]`。
>---> **`arr = [1, 5, 3, 7, 2, 6, 4]`**。

class Solution {
public:
    vector<int> beautifulArray(int N) {
        vector<int> ans = {1};
        
        while (ans.size() < N){
            vector<int> temp;
            
            for(auto val : ans)    if (val * 2 - 1 <= N) temp.push_back(val * 2 - 1);
            for(auto val : ans)    if (val * 2 <= N)     temp.push_back(val * 2);
            
            ans = temp;
        }
        return ans;
    }
};