LeetCode 932 - Beautiful Array

https://leetcode.com/problems/beautiful-array/

For some fixed N, an array A 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 A[k] * 2 = A[i] + A[j].

Given N, return any beautiful array A.  (It is guaranteed that one exists.)

Example 1:

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

Example 2:

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

http://www.noteanddata.com/leetcode-932-Beautiful-Array-java-solution-note.html

1. 首先暴力枚举肯定不过，N!的复杂度太大，枚举到10的时候一般电脑就要跑很久了。
2. 然后如果一时不知道怎么做，可能是先找beautiful array的规律和特点
3. [1]是beautiful的， [1,2]也是beautiful的, [1,3,2]也是beautiful array
4. 一个重要的规律是， 如果一个数组是beautiful的， 那么任意挑选其中的元素， 按照原来的顺序组成数组，也是beautiful array
这个比较容易理解， 整个数组里面挑选不出A[k]* 2 = A[i] + A[j]的话， 那其中一部分也一定挑选不出来。
这时候，如果我们可以构造一个大一点的数组， 那么把其中<=N的数挑选出来，就可以返回一个符合要求的结果了
5. 普遍的思路是divide and conquer, 也就是分治法，但是这个思路也不是很直观， 就直接说规律，
如果有两个小的数组A1和A2都是beautiful array的话， 那么， 能不能把这两个小的数组合并成一个beautiful array呢？
如果其中一个都是偶数， 一个都是奇数， 那么合并后一定还是一个beautiful array,
因为本身两个小数组自身都已经是beautiful array了， 所以i,j,k在自己里面找一定不存在，
然后如果是i和j在两个数组里面各取一个的话， 那么结果就是奇数， 而A[k] * 2 是偶数， 所以这一定不存在。
所以， 只要先构造一个奇数的beautiful array, 再构造一个偶数的beatiful array, 那么左右合并就是一个新的beautiful array
6. 根据前面第3条， 我们已经有N<=3的几个beautiful array， 现在只需要找到一个通用的方法构造全部是奇数的beautiful array
和全部是偶数的beautiful array 就好，
a. 那么假设已经存在一个N的beautiful array, 可以证明对于里面的每个元素做A[i] * 2 的变换以后，还是beautiful array,
因为 A[k] * 2 = A[i] + A[j] 可以得出 (A[k] * 2) * 2 != (A[i] + A[j]) * 2
b. 然后， 对每个元素做A[i] * 2 -1 的变换， 还是beautiful array,
7. 更巧的是， 如果我们从1开始做变换， 分别生成A[i] * 2的偶数数组和A[i] * 2 -1 的奇数数组， 合并以后整个数是连续的，
分别对应了合并后的所有偶数和奇数， 那么这样一直变换下去，就可以从1->2->4->8->16….
8. 根据第4条规律， 子数组也是beautiful array, 那么在变换的过程中设置一下最大值， 只取范围内的数， 然后取够了就好.
实际上这个cap只会在最后一步发生， 就是本来会生成一个N*2的数组。

循环的过程相当于生成了一个树，其中每一层分别有1,2,4,8,….N个节点， 树的高度是logN,
所以整体的复杂度是1+2+4+8….N=2N, 所以是O(2N), 也就是O(N)
更正： 之前认为“树的平均长度是N/2, 所以整体的时间复杂度是N/2 * logN”， 其实是错的。 感谢@Lee215的解释

Approach 1: Divide and Conquer

This answer is quite unintuitive.

First, notice that the condition is equivalent to saying that A has no arithmetic subsequence. We'll use the term "arithmetic-free" interchangeably with "beautiful".

One way is to guess that we should divide and conquer. One reason for this is that the condition is linear, so if the condition is satisfied by variables taking on values (1, 2, ..., n), it is satisfied by those variables taking on values (a + b, a + 2*b, a + 3*b, ..., a + (n-1)*b) instead.

If we perform a divide and conquer, then we have two parts left and right, such that each part is arithmetic-free, and we only want that a triple from both parts is not arithmetic. Looking at the conditions:

• 2*A[k] = A[i] + A[j]
• (i < k < j), i from left, j from right

we can guess that because the left hand side 2*A[k] is even, we can choose left to have all odd elements, and right to have all even elements.

Another way we could arrive at this is to try to place a number in the middle, like 5. We will have 4 and 6say, to the left of 5, and 7 to the right of 6, etc. We see that in general, odd numbers move towards one direction and even numbers towards another direction.

One final way we could arrive at this is to inspect possible answers arrived at by brute force. On experimentation, we see that many answers have all the odd elements to one side, and all the even elements to the other side, with only minor variation.

Algorithm

Looking at the elements 1, 2, ..., N, there are (N+1) / 2 odd numbers and N / 2 even numbers.

We solve for elements 1, 2, ..., (N+1) / 2 and map these numbers onto 1, 3, 5, .... Similarly, we solve for elements 1, 2, ..., N/2 and map these numbers onto 2, 4, 6, ....

We can compose these solutions by concatenating them, since an arithmetic sequence never starts and ends with elements of different parity.

We memoize the result to arrive at the answer quicker.

• Time Complexity: $O(N \log N)$. The function f is called only $O(\log N)$ times, and each time does $O(N)$ work.
• Space Complexity: $O(N \log N)$. 

  Map<Integer, int[]> memo;

  public int[] beautifulArray(int N) {

    memo = new HashMap();

    return f(N);

  }

  public int[] f(int N) {

    if (memo.containsKey(N))

      return memo.get(N);

    int[] ans = new int[N];

    if (N == 1) {

      ans[0] = 1;

    } else {

      int t = 0;

      for (int x : f((N + 1) / 2)) // odds

        ans[t++] = 2 * x - 1;

      for (int x : f(N / 2)) // evens

        ans[t++] = 2 * x;

    }

    memo.put(N, ans);

    return ans;

  }

https://leetcode.com/problems/beautiful-array/discuss/186679/C%2B%2BJavaPython-Odd-%2B-Even-Pattern-O(N)

Try to divide and conquer,
so we have left part, right part.

One way is to divide into [1, N / 2] and [N / 2 + 1, N].
But it will cause problems when we merge them.

Another way is to divide into odds part and evens part.
So there is no k with A[k] * 2 = odd + even

I brute force all permutations when N = 5:
20 beautiful array found,
only 4 don't fit odd + even pattern:
[2, 1, 4, 5, 3]
[3, 1, 2, 5, 4]
[3, 5, 4, 1, 2]
[4, 5, 2, 1, 3]

Beautiful Array Properties

Saying that an array is beautiful,
there is no i < k < j,
such that A[k] * 2 = A[i] + A[j]

Apply these 3 following changes a beautiful array,
we can get a new beautiful array

1. Deletion
Easy to prove.

2. Addition
If we have A[k] * 2 != A[i] + A[j],
(A[k] + x) * 2 = A[k] * 2 + 2x != A[i] + A[j] + 2x = (A[i] + x) + (A[j] + x)

E.g: [1,3,2] + 1 = [2,4,3].

3. Multiplication
If we have A[k] * 2 != A[i] + A[j],
(A[k] * x) * 2 = A[k] * 2 * x != (A[i] + A[j]) * x = (A[i] * x) + (A[j] * x)

E.g: [1,3,2] * 2 = [2,6,4]

Explanation

With the observations above, we can easily construct any beautiful array.
Assume we have a beautiful array A with length N

A1 = A * 2 - 1 is beautiful with only odds from 1 to N * 2 -1
A2 = A * 2 is beautiful with only even from 2 to N * 2
B = A1 + A2 beautiful array with length N * 2

E.g:

A = [2, 1, 4, 5, 3]
A1 = [3, 1, 7, 9, 5]
A2 = [4, 2, 8, 10, 6]
B = A1 + A2 = [3, 1, 7, 9, 5, 4, 2, 8, 10, 6]

Time Complexity:

I have iteration version here O(N)
Naive recursion is O(NlogN)
Recursion with one call or with cache is O(N)

    public int[] beautifulArray(int N) {
        ArrayList<Integer> res = new ArrayList<>();
        res.add(1);
        while (res.size() < N) {
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int i : res) if (i * 2 - 1 <= N) tmp.add(i * 2 - 1);
            for (int i : res) if (i * 2 <= N) tmp.add(i * 2);
            res = tmp;
        }
        return res.stream().mapToInt(i -> i).toArray();
    }

https://leetcode.com/problems/beautiful-array/discuss/186680

How it Works

It's basically an implementation of the idea from https://leetcode.com/problems/beautiful-array/discuss/186679/

When you reverse in binary & sort it, it's basically to align those even ones first, then the old ones. Doing this recursively.

An example I walked through was when N = 6, I can get: [4, 2, 6, 1, 5, 3]

Sort by reversed binary

    def beautifulArray(self, N):
        return sorted(range(1, N + 1), key=lambda x: bin(x)[:1:-1])

Naive recursion

    def beautifulArray(self, N):
        return [i * 2 for i in self.beautifulArray(N / 2)] + [i * 2 - 1 for i in self.beautifulArray((N + 1) / 2)] if N > 1 else [1]

Binary Reverse

    def beautifulArray(self, N):
        return [i for i in [int('{:010b}'.format(i)[::-1], 2) for i in range(1, 1 << 10)] if i <= N]

https://leetcode.com/problems/beautiful-array/discuss/186661/3-solutions-4-lines-in-Python-(Divide-and-Conquer)-%2B-DP-(Top-down-and-bottom-up)

Divide and conquer strategy:
l gives beautiful array of even numbers
r gives beautiful array of odd numbers

def beautifulArray(self, N):
        """
        :type N: int
        :rtype: List[int]
        """
        if N==1: return [1]
 l=self.beautifulArray(N//2)
 r=self.beautifulArray(N-N//2)
 return [x*2 for x in l]+[x*2-1 for x in r]

You can optimize this by having only 1 recrusive call :

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]

Thanks @lee215 for suggesting this.

Top-Down DP (memoization):

You can see overallping subproblems if you draw recursion tree, hence you can use memoization:

class Solution:
    memo = {}
    def beautifulArray(self, N):
        """
        :type N: int
        :rtype: List[int]
        """
        if N==1: return [1]
        if N in self.memo: return self.memo[N]
        l=self.beautifulArray(N//2)
        r=self.beautifulArray(N-N//2)
        self.memo[N] = [x*2 for x in l]+[x*2-1 for x in r]
        return self.memo[N]

DP (bottom up):
You construct the tree in bottom up manner:

def beautifulArray(self, N):
        """
        :type N: int
        :rtype: List[int]
        """
        dp = {}
        dp[1] = [1]
        for i in range(2,N+1):
            dp[i] = [x*2 for x in dp[i//2]] + [x*2-1 for x in dp[i-i//2]]
        
        return dp[N]