Wednesday, September 28, 2022
HomeSoftware DevelopmentDiscover permutation such that adjoining components has distinction of at the least...

# Discover permutation such that adjoining components has distinction of at the least 2

Given a quantity N, the duty is to discover a permutation A[] of first N integers such that absolutely the distinction of adjoining components is at the least 2 i.e., | Ai+1 − Ai | ≥ 2 for all 0 ≤ i < N−1.If no such permutation exists, print -1.

Examples:

Enter: N = 4
Output: 3 1 4 2
Clarification: Right here A[] = {3, 1, 4, 2} satisfies the given situation.
Since  | Ai+1 − Ai | ≥ 2 for all 0 ≤ i < N−1

Enter: N = 2
Output: -1
Clarification: No such permutation is feasible that satisfies the given situation

Method: The issue might be solved based mostly on the next statement:

• If N = 2 or N = 3, then no array exists that fulfill the above situation.
• In any other case, array exists that fulfill the above situation resembling:
• First print all odd numbers from N to 1 in reducing order and after that print all even numbers in reducing order.

Comply with the steps talked about under to implement the concept:

• If N = 2 or N = 3, print -1.
• In any other case, examine whether or not N is odd and even:
• If N is odd, iterate a loop from N to 1 to print all odd numbers after that iterate one other loop from N – 1 to 2 to print even numbers.
• If N is even, iterate a loop from N – 1 to 1 to print all odd numbers after that iterate one other loop from N to 2 to print even numbers.

Beneath is the implementation of the above strategy.

## Java

 ` `  `import` `java.io.*;` `import` `java.util.*;` ` `  `public` `class` `GFG {` ` `  `    ` `    ``public` `static` `void` `findArray(``int` `n)` `    ``{` `        ``if` `(n == ``2` `|| n == ``3``)` `            ``System.out.println(-``1``);` `        ``else` `{` ` `  `            ` `            ``if` `((n % ``2``) == ``1``) {` ` `  `                ` `                ``for` `(``int` `i = n; i >= ``1``; i -= ``2``) {` `                    ``System.out.print(i + ``" "``);` `                ``}` `                ``for` `(``int` `i = n - ``1``; i >= ``2``; i -= ``2``) {` `                    ``System.out.print(i + ``" "``);` `                ``}` `            ``}` ` `  `            ` `            ``else` `{` ` `  `                ` `                ``for` `(``int` `i = n - ``1``; i >= ``1``; i -= ``2``) {` `                    ``System.out.print(i + ``" "``);` `                ``}` `                ``for` `(``int` `i = n; i >= ``2``; i -= ``2``) {` `                    ``System.out.print(i + ``" "``);` `                ``}` `            ``}` `            ``System.out.println();` `        ``}` `    ``}` ` `  `    ` `    ``public` `static` `void` `most important(String[] args)` `    ``{` `        ``int` `N = ``4``;` ` `  `        ` `        ``findArray(N);` `    ``}` `}`

Time Complexity: O(N)
Auxiliary Area: O(1)

RELATED ARTICLES