Programa Cpp14 para maximizar la diferencia entre la suma de los elementos de array primos y no primos desplazando los dígitos a la izquierda un número mínimo de veces

Dada una array arr[] de tamaño N , la tarea es encontrar la diferencia máxima entre la suma de los números primos y la suma de los números no primos presentes en la array, desplazando a la izquierda los dígitos de los elementos de la array en 1 mínimo numero de veces. 

Ejemplos:

Entrada: arr[] = {541, 763, 321, 716, 143}
Salida: Diferencia = 631, Conteo de operaciones = 6
Explicación: 
Operación 1: Desplace a la izquierda los dígitos de arr[1] (= 763). Por lo tanto, arr[1] se convierte en 637.
Operación 2: Desplace a la izquierda los dígitos de arr[1] (= 637). Por lo tanto, arr[1] se convierte en 376.
Operación 3: Desplace a la izquierda los dígitos de arr[2] (= 321). Por lo tanto, arr[2] se convierte en 213.
Operación 4: Desplace a la izquierda los dígitos de arr[2] (= 213). Por lo tanto, arr[2] se convierte en 132.
Operación 5: Desplace a la izquierda los dígitos de arr[3] (= 716). Por lo tanto, arr[3] se convierte en 167.
Operación 6: Desplace a la izquierda los dígitos de arr[4] (= 143). Por lo tanto, arr[4] se convierte en 431.
Por lo tanto, Suma de elementos primos del arreglo = 541 + 167 + 431 = 1139.
Por lo tanto, suma de elementos de array no primos = 376 + 132 = 508.
Por lo tanto, diferencia = 1139 – 508 = 631.

Entrada: {396, 361, 359, 496, 780}
Salida: Diferencia = 236, Conteo de operaciones = 4
Explicación:
Operación 1: Desplazar a la izquierda los dígitos de arr[1] (= 361). Por lo tanto, arr[1] se convierte en 613.
Operación 2: Desplace a la izquierda los dígitos de arr[2] (= 359). Por lo tanto, arr[2] se convierte en 593.
Operación 3: Desplace a la izquierda los dígitos de arr[4] (= 780). Por lo tanto, arr[4] se convierte en 807.
Operación 4: Desplace a la izquierda los dígitos de arr[4] (= 807). Por lo tanto, arr[4] se convierte en 078.
Por lo tanto, diferencia requerida = 613 + 593 – 496 – 78 – 396 = 236.

Enfoque: El problema dado se puede resolver con avidez . Si es posible convertir un elemento en uno o más de un número primo , entonces tome el máximo de ellos. De lo contrario, intente minimizar el elemento utilizando todas las rotaciones posibles.
Siga los pasos a continuación para resolver el problema:

• Inicialice dos variables, digamos ans y cost, para almacenar la diferencia máxima y el número mínimo de operaciones requeridas respectivamente.
• Recorra la array arr[] usando una variable i y realice los siguientes pasos:
  • Inicialice las variables maxPrime y minRotation como -1 para almacenar el número primo máximo y el número mínimo que se puede obtener de arr[i] mediante rotaciones a la izquierda.
  • Genera todas las rotaciones a la izquierda del número arr[i] .
    • Si arr[i] es un número primo que excede maxPrime , actualice maxPrime a arr[i] y el costo correspondiente.
  • Si el valor de maxPrime permanece sin cambios, encuentre el valor de minRotation generando de manera similar todas las rotaciones a la izquierda.
  • Agregue el valor de arr[i] a ans .
• Después de completar los pasos anteriores, imprima el valor de ans y el costo como resultado.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to check if a
// number is prime or not
bool isPrime(int n)
{
  
    // Base cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
  
    // Check if the number is
    // a multiple of 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;
  
    int i = 5;
  
    // Iterate until square root of n
    while (i * i <= n) {
  
        // If n is divisible by both i and i + 2
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
        i = i + 6;
    }
    return true;
}
  
// Function to left shift a number
// to maximize its contribution
pair<int, int> rotateElement(int n)
{
  
    // Convert the number to string
    string strN = to_string(n);
  
    // Stores the maximum prime number
    // that can be obtained from n
    int maxPrime = -1;
  
    // Store the required
    // number of operations
    int cost = 0;
  
    string temp = strN;
  
    // Check for all the left
    // rotations of the number
    for (int i = 0; i < strN.size(); i++) {
  
        // If the number is prime, then
        // take the maximum among them
        if (isPrime(stoi(temp)) && stoi(temp) > maxPrime) {
            maxPrime = stoi(temp);
            cost = i;
        }
  
        // Left rotation
        temp = temp.substr(1) + temp[0];
    }
  
    int optEle = maxPrime;
  
    // If no prime number can be obtained
    if (optEle == -1) {
        optEle = INT_MAX;
        temp = strN;
  
        // Check all the left
        // rotations of the number
        for (int i = 0; i < strN.size(); i++) {
  
            // Take the minimum element
            if (stoi(temp) < optEle) {
                optEle = stoi(temp);
                cost = i;
            }
  
            // Left rotation
            temp = temp.substr(1) + temp[0];
        }
        optEle *= (-1);
    }
  
    return { optEle, cost };
}
  
// Function to find the maximum sum
// obtained using the given operations
void getMaxSum(int arr[], int N)
{
  
    // Store the maximum sum and
    // the number of operations
    int maxSum = 0, cost = 0;
  
    // Traverse array elements
    for (int i = 0; i < N; i++) {
        int x = arr[i];
  
        // Get the optimal element and the
        // number of operations to obtain it
        pair<int, int> ret = rotateElement(x);
  
        int optEle = ret.first, optCost = ret.second;
  
        // Increment the maximum difference
        // and number of operations required
        maxSum += optEle;
        cost += optCost;
    }
  
    // Print the result
    cout << "Difference = " << maxSum << " , "
         << "Count of operations = " << cost;
}
  
// Driven Program
int main()
{
    // Given array arr[]
    int arr[] = { 541, 763, 321, 716, 143 };
  
    // Store the size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
  
    // Function call
    getMaxSum(arr, N);
  
    return 0;
}

Difference = 631 , Count of operations = 6

Complejidad de tiempo: O(N*√X*log(X)), donde X es el elemento más grande de la array
Espacio auxiliar: O(1)

¡Consulte el artículo completo sobre Maximizar la diferencia entre la suma de elementos de array primos y no primos desplazando los dígitos a la izquierda un número mínimo de veces para obtener más detalles!