DSA sheet / Introductory
Permutations
The problem in brief
Given n (up to a million), output any ordering of the numbers 1 to n in which adjacent numbers never differ by exactly 1. If no such ordering exists, print NO SOLUTION. Any valid ordering is accepted.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1070.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Try tiny n by hand: 1, 2, 3, 4, 5. Which of them are impossible? The impossible ones are few and easy to list.
-
Two numbers differ by 1 exactly when they have different parity and sit next to each other in value. What if consecutive numbers in your output all had the same parity?
-
Group the numbers by parity. Within one group, neighbours in the output can be chosen so that they differ by 2. Only the seam between the two groups needs care.
-
Put all the evens first, then all the odds. Check the seam: the last even and the first odd. When does that pair differ by 1?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Constructive problems reward exploring small cases and hunting for structure, not for search. Brute force over all n! permutations is out for anything past 10, so ask what structure forbids “differ by 1”. The answer is parity: two numbers that differ by 1 always have opposite parity. If you write all numbers of one parity in a row, they trivially differ by even amounts.
That leaves one seam. Trying n = 2 and 3 by hand shows no arrangement works (2 numbers are consecutive; for 3, the number 2 is adjacent to one of its neighbours in value wherever it goes). From n = 4 on, the seam between “last even” and “first odd” is between a number at least 4 and the number 1, which are far apart. That is the whole solution.
The habit: split the universe by an invariant that makes the forbidden relation impossible inside each part, then check only the junctions.
Intuition
Two lines of people: all the even-numbered ones, then all the odd-numbered ones. Inside a line nobody is next to their numeric neighbour. The only place two people meet across lines is the join, and with at least four people the join pairs a large even number with 1.
Approach
- If n is 1, print
1. - If n is 2 or 3, print
NO SOLUTION. - Otherwise print 2, 4, 6, … up to n, then 1, 3, 5, … up to n.
Edge cases: n = 1 is valid (a single number has no neighbours). For n = 4 the answer 2 4 1 3 has seam 4 to 1, difference 3. Build the output in one buffer, since n can be a million.
Complexity
O(n) time and O(n) output.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
if (n == 1) {
puts("1");
} else if (n <= 3) {
puts("NO SOLUTION");
} else {
string out;
for (int i = 2; i <= n; i += 2) out += to_string(i) + " ";
for (int i = 1; i <= n; i += 2) out += to_string(i) + " ";
out.pop_back();
puts(out.c_str());
}
return 0;
}import sys
def main():
n = int(sys.stdin.readline())
if n == 1:
print(1)
elif n <= 3:
print("NO SOLUTION")
else:
print(" ".join(map(str, list(range(2, n + 1, 2)) + list(range(1, n + 1, 2)))))
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine().trim());
if (n == 1) {
System.out.println(1);
} else if (n <= 3) {
System.out.println("NO SOLUTION");
} else {
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= n; i += 2) sb.append(i).append(' ');
for (int i = 1; i <= n; i += 2) sb.append(i).append(' ');
sb.setLength(sb.length() - 1);
System.out.println(sb);
}
}
}const n = Number(require('fs').readFileSync(0, 'utf8').trim());
if (n === 1) {
console.log('1');
} else if (n <= 3) {
console.log('NO SOLUTION');
} else {
const out = [];
for (let i = 2; i <= n; i += 2) out.push(i);
for (let i = 1; i <= n; i += 2) out.push(i);
console.log(out.join(' '));
}Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).