首页 > 文章列表 > 安排前N个自然数,使得相邻元素的绝对差大于1

安排前N个自然数,使得相邻元素的绝对差大于1

自然数 相邻元素 绝对差
451 2023-08-19

We have the first N natural numbers. Our task is to get one permutation of them where the absolute difference between every two consecutive elements is > 1. If no such permutation is present, return -1.

The approach is simple. We will use the greedy approach. We will arrange all odd numbers in increasing or decreasing order, then arrange all even numbers in decreasing or increasing order

Algorithm

arrangeN(n)

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

Example

的中文翻译为:

示例

#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);
}

Output

7 5 3 1 8 6 4 2