932. 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]

 

Note:

  • 1 <= N <= 1000
 

Rust Solution

struct Solution;

impl Solution {
    fn beautiful_array(n: i32) -> Vec<i32> {
        if n == 1 {
            vec![1]
        } else {
            let left = Self::beautiful_array(n / 2);
            let right = Self::beautiful_array((n + 1) / 2);
            left.into_iter()
                .map(|x| x * 2)
                .chain(right.into_iter().map(|x| x * 2 - 1))
                .collect()
        }
    }
}

#[test]
fn test() {
    let n = 4;
    let res = vec![4, 2, 3, 1];
    assert_eq!(Solution::beautiful_array(n), res);
}

Having problems with this solution? Click here to submit an issue on github.