Challenge

Given an integer n ≥ 4, output a permutation of the integers [0, n-1] with the property that no two consecutive integers are next to each other.

Examples

• 4 → [1, 3, 0, 2]
• 5 → [0, 2, 4, 1, 3]
• 6 → [0, 2, 4, 1, 3, 5]
• 7 → [0, 2, 4, 1, 5, 3, 6]

You may use 1-indexing instead (using integers [1, n] instead of [0, n-1]).

Your code must run in polynomial time in n, so you can't try all permutations and test each one.

Challenge

Given an integer n ≥ 4, output a permutation of the integers [0, n-1] with the property that no two consecutive integers (integers with absolute difference 1) are next to each other.

Examples

• 4 → [1, 3, 0, 2]
• 5 → [0, 2, 4, 1, 3]
• 6 → [0, 2, 4, 1, 3, 5]
• 7 → [0, 2, 4, 1, 5, 3, 6]

You may use 1-indexing instead (using integers [1, n] instead of [0, n-1]).

Your code must run in polynomial time in n, so you can't try all permutations and test each one.

Challenge

Given an integer n, output a permutation of the integers 0 to n - 1 with the property that no two consecutive integers are next to each other. You can assume n >= 4.

Examples

• For n = 4. (1, 3, 0, 2)
• For n = 5. (0, 2, 4, 1, 3)
• For n = 6. (0, 2, 4, 1, 3, 5)
• For n = 7. (0, 2, 4, 1, 5, 3, 6)

You may use 1-indexing instead (using integers 1 to n, instead of 0 to n-1).

Your code must run in polynomial time in n. For this who don't speak computational complexity, you can take this rule to mean that your code can't try all permutations and test each one.

Challenge

Given an integer n ≥ 4, output a permutation of the integers [0, n-1] with the property that no two consecutive integers are next to each other.

Examples

• 4 → [1, 3, 0, 2]
• 5 → [0, 2, 4, 1, 3]
• 6 → [0, 2, 4, 1, 3, 5]
• 7 → [0, 2, 4, 1, 5, 3, 6]

You may use 1-indexing instead (using integers [1, n] instead of [0, n-1]).

Your code must run in polynomial time in n, so you can't try all permutations and test each one.