Construct a permutation of 1..n such that no element is the average of two others.
Beautiful Array
Given an integer n, build any permutation of the integers from 1 to n such that for every triple of indices i < k < j, it is not true that
In other words, no element should be the midpoint of two other elements that appear on its left and right.
Return one valid beautiful array of length n.
A valid answer always exists.
Input Format
- A single integer
n. - You must produce a permutation of the integers
1..n.
Output Format
- Return any permutation
Aof lengthnsuch that there is no triplei < k < jwith2 * A[k] = A[i] + A[j].
Constraints
1 <= n- The intended solution is efficient for large
n. - The returned array must contain each integer from
1tonexactly once.
Example 1
Input
n = 4
Output
[1, 3, 2, 4]
Explanation
This is a permutation of 1..4. No element is the average of two elements with one on each side.
Example 2
Input
n = 5
Output
[1, 5, 3, 2, 4]
Explanation
This is also a valid beautiful array. For every i < k < j, A[k] is never the midpoint of A[i] and A[j].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.