Beautiful Array

medium math divide and conquer recursion

Problem

An array nums of length n is beautiful if it is a permutation of the integers 1..n and there is no triple of indices i < k < j with 2·nums[k] == nums[i] + nums[j] (no element is the average of two elements flanking it). For a given n, return any beautiful array.

Inputn = 4

Output[1, 3, 2, 4]

All odd values come before all even values, so no element equals the average of one earlier and one later element.

n (1..16)

def beautiful_array(n):
    res = [1]
    while len(res) < n:
        odds = [2 * x - 1 for x in res]
        evens = [2 * x for x in res]
        res = [x for x in odds + evens if x <= n]
    return res

function beautifulArray(n) {
  let res = [1];
  while (res.length < n) {
    const odds = res.map(x => 2 * x - 1);
    const evens = res.map(x => 2 * x);
    res = odds.concat(evens).filter(x => x <= n);
  }
  return res;
}

class Solution {
    public int[] beautifulArray(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(1);
        while (res.size() < n) {
            List<Integer> next = new ArrayList<>();
            for (int x : res) if (2 * x - 1 <= n) next.add(2 * x - 1);
            for (int x : res) if (2 * x <= n) next.add(2 * x);
            res = next;
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

vector<int> beautifulArray(int n) {
    vector<int> res = {1};
    while ((int)res.size() < n) {
        vector<int> next;
        for (int x : res) if (2 * x - 1 <= n) next.push_back(2 * x - 1);
        for (int x : res) if (2 * x <= n) next.push_back(2 * x);
        res = next;
    }
    return res;
}

Explanation

We want a permutation of 1..n with no element sitting exactly between two others (no i < k < j with 2*nums[k] == nums[i] + nums[j]). The trick is to keep all odd-derived numbers before all even-derived numbers, building up from a tiny solved case.

The key fact: if you already have a beautiful array, you can double its size. Map each value x to 2x - 1 to get an all-odd list, and to 2x to get an all-even list. Both new lists are still beautiful, and odds come first, evens second.

Why does the split work? Any average lies strictly between two numbers, so a "bad triple" would need the middle value to equal the average of the outer two. But odd + even is always odd, never twice an even, so no triple can straddle the odd/even boundary. Inside each half the property holds by induction.

We start with res = [1] and repeat the doubling, filtering out anything larger than n, until res has n elements.

Example: n = 4. From [1] we get odds [1] and evens [2] → [1, 2]; doubling again gives odds [1, 3] and evens [2, 4] → [1, 3, 2, 4], a valid beautiful array.

Time: O(n log n) Space: O(n)