Horje
Constructing Palindromic Arrays with First Element as X

Given two integers N and X (1 <= X <= N). The task is to find a permutation P of [1,2,3…N] with the first element as X, such that the difference array Diff[], where Diffi = P(i+1) – Pi for all i (1 <= i < N), forms a palindrome. If no such permutation exists, output -1.

Examples:

Input: N = 4, X = 3
Output: P[] = {3, 1, 4, 2}
Explanation: If P[] = {3, 1, 4, 2}, Then:

  • First element of P[] is equal to X = 3, which is true.
  • Calculating Diff[] for all i (1 <= i < N) gives = {(P2-P1), (P3-P2), (P4-P3)} = {(1-3), (4-1), (2-4)} = {-2, 3, -2}, which is palindrome.

Thus, P[] follows all the conditions, having length N and all elements are from the range [1, N].

Input: N = 3, X = 2
Output: -1
Explanation: It can be verified that no such P[] exists for the given values of N and X.

Approach:

The problem is observation based. The main idea is:

  • If N is odd and X is equal to (N + 1)/2, then no such P[] exists.
  • Otherwise, a possible permutation P[] will always be there. Which can be obtained by following below sequence:
    • First, we have to print the X.
    • Then print all numbers from 1 to N except X and (N – X + 1).
    • Finally print (N – X + 1).

Step-by-step approach:

  • Check Special Case:
    • If N is odd and X is equal to (N + 1) / 2, output -1.
  • Generate Permutation:
    • Calculate Y = N – X + 1.
    • Print X.
    • Print all numbers from 1 to N except X and Y.
    • Print Y.

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
#include <iostream>
using namespace std;
 
// Method to output P[], If it is possible
void Find_permutation(int N, int X)
{
    // First condition, where N is odd and X is equal to
    // (N+1)/2
    if (N % 2 == 1 && X == (N + 1) / 2) {
        cout << -1;
        return;
    }
 
    // Else we are making the following arrangement by code
    // below: First, we have to print the X. Then print all
    // numbers from 1 to N except X and (N - X + 1). Finally
    // print (N - X + 1).
    int Y = N - X + 1;
 
    // First element of arrangement
    cout << X << " ";
 
    // printing all numbers from 1 to N except X and (N - X
    // + 1).
    for (int i = 1; i <= N; ++i) {
        if (i == X || i == Y)
            continue;
        cout << i << " ";
    }
 
    // Finally printing (N - X + 1)
    cout << Y << " ";
}
 
// Driver Function
int main()
{
    // Input
    int N = 4, X = 4;
 
    // Function_call
    Find_permutation(N, X);
    return 0;
}
 
// This code is contributed by ragul21

Java

// Java code to implement the approach
import java.util.*;
 
// Driver Class
public class GFG {
    // Driver Function
    public static void main(String[] args)
    {
        // Input
        int N = 4, X = 4;
 
        // Function_call
        Find_permutation(N, X);
    }
 
    // Method to output P[], If it is possible
    public static void Find_permutation(int N, int X)
    {
       
        //First condition, where N is odd and X is equal to
        // (N+1)/2
        if (N % 2 == 1 && X == (N + 1) / 2) {
            System.out.println(-1);
            return;
        }
       
        //Else we are making the following arrangement by code below:
        //First, we have to print the X.
        //Then print all numbers from 1 to N except X and (N - X + 1).
        //Finally print (N - X + 1).
        int Y = N - X + 1;
       
        //First element of arrangement
        System.out.print(X + " ");
       
        // printing all numbers from 1 to N except X and (N - X + 1).
        for (int i = 1; i <= N; ++i) {
            if (i == X || i == Y)
                continue;
            System.out.print(i + " ");
        }
       
        //Finally printing (N - X + 1)
        System.out.print(Y + " ");
    }
}

Python3

# Method to output P[], If it is possible
def find_permutation(N, X):
    # First condition, where N is odd and X is equal to
    # (N+1)/2
    if N % 2 == 1 and X == (N + 1) // 2:
        print(-1)
        return
 
    # Else we are making the following arrangement by code
    # below: First, we have to print the X. Then print all
    # numbers from 1 to N except X and (N - X + 1). Finally
    # print (N - X + 1).
    Y = N - X + 1
 
    # First element of arrangement
    print(X, end=" ")
 
    # printing all numbers from 1 to N except X and (N - X
    # + 1).
    for i in range(1, N + 1):
        if i == X or i == Y:
            continue
        print(i, end=" ")
 
    # Finally printing (N - X + 1)
    print(Y, end=" ")
 
# Driver Function
if __name__ == "__main__":
    # Input
    N = 4
    X = 4
 
    # Function call
    find_permutation(N, X)
 
# This code is contributed by akshitaguprzj3

C#

// C# code to implement the approach
using System;
 
class GFG
{
    // Method to output P[], If it is possible
    static void FindPermutation(int N, int X)
    {
        // First condition, where N is odd and X is equal to
        // (N+1)/2
        if (N % 2 == 1 && X == (N + 1) / 2)
        {
            Console.WriteLine(-1);
            return;
        }
 
        // Else we are making the following arrangement by code
        // below: First, we have to print the X. Then print all
        // numbers from 1 to N except X and (N - X + 1). Finally
        // print (N - X + 1).
        int Y = N - X + 1;
 
        // First element of arrangement
        Console.Write(X + " ");
 
        // printing all numbers from 1 to N except X and (N - X
        // + 1).
        for (int i = 1; i <= N; ++i)
        {
            if (i == X || i == Y)
                continue;
            Console.Write(i + " ");
        }
 
        // Finally printing (N - X + 1)
        Console.Write(Y + " ");
    }
 
    // Driver Function
    static void Main()
    {
        // Input
        int N = 4, X = 4;
 
        // Function_call
        FindPermutation(N, X);
    }
}

Javascript

// Method to output P[], If it is possible
function findPermutation(N, X) {
    // First condition, where N is odd and X is equal to (N+1)/2
    if (N % 2 === 1 && X === Math.floor((N + 1) / 2)) {
        console.log(-1);
        return;
    }
 
    // Else we are making the following arrangement by code below:
    // First, we have to print the X.
    // Then print all numbers from 1 to N except X and (N - X + 1).
    // Finally print (N - X + 1).
    const Y = N - X + 1;
 
    // First element of arrangement
    process.stdout.write(X + " ");
 
    // Printing all numbers from 1 to N except X and (N - X + 1).
    for (let i = 1; i <= N; ++i) {
        if (i === X || i === Y)
            continue;
        process.stdout.write(i + " ");
    }
 
    // Finally printing (N - X + 1)
    console.log(Y + " ");
}
 
// Driver Function
function main() {
    // Input
    const N = 4, X = 4;
 
    // Function call
    findPermutation(N, X);
}
 
 
main();
 
// This code is contributed by shivamgupta310570

Output

4 2 3 1

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




Reffered: https://www.geeksforgeeks.org

Arrays

Related
Find sum of count of duplicate numbers in all subarrays of given array Find sum of count of duplicate numbers in all subarrays of given array
Minimize the maximum value in array by incrementing and decrementing. Minimize the maximum value in array by incrementing and decrementing.
Find triplet (i, j, k) to maximize (P * arr[i] + Q * arr[j] + R * arr[k]) Find triplet (i, j, k) to maximize (P * arr[i] + Q * arr[j] + R * arr[k])
Minimum cost to convert all characters of given binary array equal Minimum cost to convert all characters of given binary array equal
Split the array into N subarrays where each subarray has size 1 or sum at least K Split the array into N subarrays where each subarray has size 1 or sum at least K

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje