Maximice el módulo reemplazando pares adyacentes con su módulo para cualquier permutación de Array dado

Dada una array A[] que consta de elementos distintos, la tarea es obtener el valor de módulo más grande posible que queda después de reemplazar repetidamente los elementos adyacentes por su módulo, comenzando desde el primer elemento, para cualquier permutación posible de la array dada .

 (…(( A[1] modo A[2]) modo A[3]) …. ) modo A[N])

Ejemplos:

Entrada: A[] = {7, 10, 12}
Salida: 7
Explicación: Todos los valores posibles de la expresión dada en todas las permutaciones de la array dada son los siguientes:
{7, 10, 12} = ((7 % 10) % 12) = 7
{10, 12 7} = ((10 % 12) % 7) = 3
{7, 12, 10} =((7 % 12) % 10) = 7
{10, 7, 12} = ((10 % 7) % 12) = 3
{12, 7, 10} = ((12 % 7) % 10) = 5
{12, 10, 7} = ((12 % 10) % 7) = 2
Por lo tanto , el valor máximo posible es 7.

Entrada: A[] = {20, 30}
Salida: 20
Explicación:
El valor máximo posible de todas las permutaciones de la array dada es 20.

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las permutaciones de la array dada y encontrar el valor de la expresión dada para todas las permutaciones. Finalmente, imprima el valor máximo de la expresión obtenida. 
Complejidad temporal: O(N * N!) 
Espacio auxiliar: O(N)

Enfoque eficiente: Para optimizar el enfoque anterior, es necesario hacer las siguientes observaciones:

• Para cualquier permutación A ₁ …..A _N , el valor de la expresión siempre se encuentra en el rango [0, min(A ₂ …..A _n )-1] .
• Considerando que K es el elemento más pequeño del arreglo, el valor de la expresión siempre será K para las permutaciones que tengan a K como primer elemento.
• Para todas las demás permutaciones, el valor de la expresión siempre será menor que K , como se muestra en los ejemplos anteriores. Por lo tanto, K es el valor máximo posible de la expresión para cualquier permutación del arreglo.
• Por lo tanto, el valor máximo posible siempre será igual al elemento más pequeño de la array.

Por lo tanto, para resolver el problema, simplemente recorra la array y encuentre el elemento mínimo presente en la array e imprímalo como la respuesta requerida.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// of two numbers
int min(int a, int b)
{
    return (a > b) ? b : a;
}
 
// Function to find the maximum value
// possible of the given expression
// from all permutations of the array
int maximumModuloValue(int A[], int n)
{
    // Stores the minimum value
    // from the array
    int mn = INT_MAX;
    for (int i = 0; i < n; i++) {
        mn = min(A[i], mn);
    }
 
    // Return the answer
    return mn;
}
 
// Driver Code
int main()
{
    int A[] = { 7, 10, 12 };
 
    int n = (sizeof(A) / (sizeof(A[0])));
 
    cout << maximumModuloValue(A, n)
         << endl;
 
    return 0;
}

// Java Program to implement
// the above approach
import java.io.*;
class GFG{
 
    // Function to find the maximum value
    // possible of the given expression
    // from all permutations of the array
    static int maximumModuloValue(int A[], int n)
    {
        // Stores the minimum value
        // from the array
        int mn = Integer.MAX_VALUE;
 
        for (int i = 0; i < n; i++)
        {
            mn = Math.min(A[i], mn);
        }
 
        // Return the answer
        return mn;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int A[] = {7, 10, 12};
        int n = A.length;
        System.out.println(maximumModuloValue(A, n));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 program to implement
# the above approach
import sys
 
# Function to find the maximum value
# possible of the given expression
# from all permutations of the array
def maximumModuloValue(A, n):
 
    # Stores the minimum value
    # from the array
    mn = sys.maxsize
    for i in range(n):
        mn = min(A[i], mn)
 
    # Return the answer
    return mn
 
# Driver Code
 
# Given array arr[]
A = [ 7, 10, 12 ]
 
n = len(A)
 
# Function call
print(maximumModuloValue(A, n))
 
# This code is contributed by Shivam Singh

// C# Program to implement
// the above approach
using System;
class GFG{
 
  // Function to find the maximum value
  // possible of the given expression
  // from all permutations of the array
  static int maximumModuloValue(int []A,
                                int n)
  {
    // Stores the minimum value
    // from the array
    int mn = int.MaxValue;
 
    for (int i = 0; i < n; i++)
    {
      mn = Math.Min(A[i], mn);
    }
 
    // Return the answer
    return mn;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int []A = {7, 10, 12};
    int n = A.Length;
    Console.WriteLine(maximumModuloValue(A, n));
  }
}
 
// This code is contributed by shikhasingrajput

<script>
// javascript Program to implement
// the above approach
 
    // Function to find the maximum value
    // possible of the given expression
    // from all permutations of the array
    function maximumModuloValue(A , n) {
        // Stores the minimum value
        // from the array
        var mn = Number.MAX_VALUE;
 
        for (i = 0; i < n; i++) {
            mn = Math.min(A[i], mn);
        }
 
        // Return the answer
        return mn;
    }
 
    // Driver Code
     
        var A = [ 7, 10, 12 ];
        var n = A.length;
        document.write(maximumModuloValue(A, n));
 
// This code contributed by umadevi9616
</script>

7

Complejidad temporal: O(N)
Espacio auxiliar: O(1)