We have the first N natural numbers. Our task is to obtain a permutation of them where the absolute difference between every two consecutive elements is > 1. If no such arrangement exists, -1 is returned.
The method is very simple. We will use the greedy method. We sort all the odd numbers in ascending or descending order, and then sort all the even numbers in descending or ascending order
Begin if N is 1, then return 1 if N is 2 or 3, then return -1 as no such permutation is not present even_max and odd_max is set as max even and odd number less or equal to n arrange all odd numbers in descending order arrange all even numbers in descending order End
#include <iostream> using namespace std; void arrangeN(int N) { if (N == 1) { //if N is 1, only that will be placed cout << "1"; return; } if (N == 2 || N == 3) { //for N = 2 and 3, no such permutation is available cout << "-1"; return; } int even_max = -1, odd_max = -1; //find max even and odd which are less than or equal to N if (N % 2 == 0) { even_max = N; odd_max = N - 1; } else { odd_max = N; even_max = N - 1; } while (odd_max >= 1) { //print all odd numbers in decreasing order cout << odd_max << " "; odd_max -= 2; } while (even_max >= 2) { //print all even numbers in decreasing order cout << even_max << " "; even_max -= 2; } } int main() { int N = 8; arrangeN(N); }
7 5 3 1 8 6 4 2
The above is the detailed content of Arrange the first N natural numbers so that the absolute difference between adjacent elements is greater than 1. For more information, please follow other related articles on the PHP Chinese website!