Maximice K para hacer un palíndromo de array dado cuando cada elemento se reemplaza por su resto con K

Dada una array A[] que contiene N enteros positivos, la tarea es encontrar el mayor número posible K , tal que después de reemplazar todos los elementos por los elementos módulo K(A[i]=A[i]%K, para todo 0< =i<N), la array se convierte en un palíndromo . Si K es infinitamente grande, imprima -1.

Ejemplos:

Entrada: A={1, 2, 3, 4}, N=4
Salida:
1
Explicación:
Para K=1, A se convierte en {1%1, 2%1, 3%1, 4%1}={0, 0, 0, 0} que es una array palindrómica. 

Entrada: A={1, 2, 3, 2, 1}, N=5
Salida:
-1

Observación: Las siguientes observaciones ayudan a resolver el problema:

1. Si la array ya es un palíndromo, K puede ser infinitamente grande.
2. Dos números, digamos A y B , pueden hacerse iguales tomando su módulo con su diferencia (|AB|) , así como los factores de su diferencia.

Enfoque: El problema puede resolverse igualando K al MCD de las diferencias absolutas de A[i] y A[Ni-1]. Siga los pasos a continuación para resolver el problema:

1. Compruebe si A ya es un palíndromo. Si es así, devuelve -1 .
2. Almacene la diferencia absoluta del primer y último elemento de la array en una variable, digamos K , que almacenará el número más grande requerido para convertir A en un palíndromo.
3. Recorra de 1 a N/2-1 , y para cada índice actual i, haga lo siguiente:
   1. Actualice K con el GCD de K y la diferencia absoluta de A[i] y A[Ni-1].
4. Vuelve K. _

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// utility function to calculate the GCD of two numbers
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
// Function to calculate the largest K, replacing all
// elements of an array A by their modulus with K, makes A a
// palindromic array
int largestK(int A[], int N)
{
    // check if A is palindrome
    int l = 0, r = N - 1, flag = 0;
    while (l < r) {
        // A is not palindromic
        if (A[l] != A[r]) {
            flag = 1;
            break;
        }
        l++;
        r--;
    }
    // K can be infitely large in this case
    if (flag == 0)
        return -1;
 
    // variable to store the largest K that makes A
    // palindromic
    int K = abs(A[0] - A[N - 1]);
    for (int i = 1; i < N / 2; i++)
        K = gcd(K, abs(A[i] - A[N - i - 1]));
    // return the required answer
    return K;
}
// Driver code
int main()
{
    // Input
    int A[] = { 1, 2, 3, 2, 1 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function call
    cout << largestK(A, N) << endl;
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Utility function to calculate the GCD
// of two numbers
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
// Function to calculate the largest K,
// replacing all elements of an array A
// by their modulus with K, makes A a
// palindromic array
static int largestK(int A[], int N)
{
     
    // Check if A is palindrome
    int l = 0, r = N - 1, flag = 0;
    while (l < r)
    {
         
        // A is not palindromic
        if (A[l] != A[r])
        {
            flag = 1;
            break;
        }
        l++;
        r--;
    }
     
    // K can be infitely large in this case
    if (flag == 0)
        return -1;
 
    // Variable to store the largest K
    // that makes A palindromic
    int K = Math.abs(A[0] - A[N - 1]);
    for(int i = 1; i < N / 2; i++)
        K = gcd(K, Math.abs(A[i] - A[N - i - 1]));
         
    // Return the required answer
    return K;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Input
    int A[] = { 1, 2, 3, 2, 1 };
    int N = A.length;
     
    // Function call
    System.out.println(largestK(A, N));
}
}
 
// This code is contributed by sanjoy_62

# Python3 program for the above approach
 
# utility function to calculate the GCD of two numbers
def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)
       
# Function to calculate the largest K, replacing all
# elements of an array A by their modulus with K, makes A a
# palindromic array
def largestK(A, N):
   
    # check if A is palindrome
    l,r,flag = 0, N - 1, 0
    while (l < r):
        # A is not palindromic
        if (A[l] != A[r]):
            flag = 1
            break
        l += 1
        r -= 1
    # K can be infitely large in this case
    if (flag == 0):
        return -1
 
    # variable to store the largest K that makes A
    # palindromic
    K = abs(A[0] - A[N - 1])
    for i in range(1,N//2):
        K = gcd(K, abs(A[i] - A[N - i - 1]))
     
    # return the required answer
    return K
   
# Driver code
if __name__ == '__main__':
    # Input
    A= [1, 2, 3, 2, 1 ]
    N = len(A)
 
    # Function call
    print (largestK(A, N))
 
# This code is contributed by mohit kumar 29.

// c# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// utility function to calculate the GCD of two numbers
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
   
// Function to calculate the largest K, replacing all
// elements of an array A by their modulus with K, makes A a
// palindromic array
static int largestK(int []A, int N)
{
   
    // check if A is palindrome
    int l = 0, r = N - 1, flag = 0;
    while (l < r) {
        // A is not palindromic
        if (A[l] != A[r]) {
            flag = 1;
            break;
        }
        l++;
        r--;
    }
   
    // K can be infitely large in this case
    if (flag == 0)
        return -1;
 
    // variable to store the largest K that makes A
    // palindromic
    int K = Math.Abs(A[0] - A[N - 1]);
    for (int i = 1; i < N / 2; i++)
        K = gcd(K, Math.Abs(A[i] - A[N - i - 1]));
   
    // return the required answer
    return K;
}
 
// Driver code
public static void Main()
{
   
    // Input
    int []A = { 1, 2, 3, 2, 1 };
    int N = A.Length;
 
    // Function call
    Console.Write(largestK(A, N));
}
}
 
// This code is contributed by ipg2016107.

<script>
 
// Javascript program for the above approach
 
// utility function to calculate the
// GCD of two numbers
function gcd(a, b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
// Function to calculate the largest
// K, replacing all elements of an
// array A by their modulus with K,
// makes A a palindromic array
function largestK(A, N)
{
     
    // Check if A is palindrome
    let l = 0, r = N - 1, flag = 0;
     
    while (l < r)
    {
         
        // A is not palindromic
        if (A[l] != A[r])
        {
            flag = 1;
            break;
        }
        l++;
        r--;
    }
     
    // K can be infitely large in this case
    if (flag == 0)
        return -1;
 
    // Variable to store the largest K
    // that makes A palindromic
    let K = Math.abs(A[0] - A[N - 1]);
    for(let i = 1; i < N / 2; i++)
        K = gcd(K, Math.abs(A[i] - A[N - i - 1]));
         
    // Return the required answer
    return K;
}
 
// Driver code
 
// Input
let A = [ 1, 2, 3, 2, 1 ];
let N = A.length;
 
// Function call
document.write(largestK(A, N) + "<br>");
 
// This code is contributed by gfgking
 
</script>

-1

Complejidad de tiempo: O(NLogM), donde M es el elemento más grande de la array
Espacio auxiliar: O(1)