Maximice la diferencia entre la suma de los elementos primos y no primos de la array desplazando los dígitos a la izquierda el 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;
}

// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
    // Function to check if a
    // number is prime or not
    static boolean 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
    static int[] rotateElement(int n)
    {
 
        // Convert the number to string
        String strN = Integer.toString(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.length(); i++) {
 
            // If the number is prime, then
            // take the maximum among them
            if (isPrime(Integer.parseInt(temp))
                && Integer.parseInt(temp) > maxPrime) {
                maxPrime = Integer.parseInt(temp);
                cost = i;
            }
 
            // Left rotation
            temp = temp.substring(1) + temp.charAt(0);
        }
 
        int optEle = maxPrime;
 
        // If no prime number can be obtained
        if (optEle == -1) {
            optEle = Integer.MAX_VALUE;
            temp = strN;
 
            // Check all the left
            // rotations of the number
            for (int i = 0; i < strN.length(); i++) {
 
                // Take the minimum element
                if (Integer.parseInt(temp) < optEle) {
                    optEle = Integer.parseInt(temp);
                    cost = i;
                }
 
                // Left rotation
                temp = temp.substring(1) + temp.charAt(0);
            }
            optEle *= (-1);
        }
        return new int[] { optEle, cost };
    }
 
    // Function to find the maximum sum
    // obtained using the given operations
    static void getMaxSum(int arr[])
    {
 
        // Store the maximum sum and
        // the number of operations
        int maxSum = 0, cost = 0;
 
        // Traverse array elements
        for (int x : arr) {
 
            // Get the optimal element and the
            // number of operations to obtain it
            int ret[] = rotateElement(x);
 
            int optEle = ret[0], optCost = ret[1];
 
            // Increment the maximum difference
            // and number of operations required
            maxSum += optEle;
            cost += optCost;
        }
 
        // Print the result
        System.out.println("Difference = " + maxSum + " , "
                           + "Count of operations = "
                           + cost);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given array arr[]
        int arr[] = { 541, 763, 321, 716, 143 };
 
        // Function call
        getMaxSum(arr);
    }
}

# Python program for the above approach
 
# Function to check if a
# number is prime or not
def isPrime(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 or n % 3 == 0):
        return False
 
    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 or n % (i + 2) == 0):
            return False
        i = i + 6
 
    return True
 
# Function to left shift a number
# to maximize its contribution
def rotateElement(n):
 
        # Convert the number to string
    strN = str(n)
 
    # Stores the maximum prime number
    # that can be obtained from n
    maxPrime = -1
 
    # Store the required
    # number of operations
    cost = 0
 
    temp = str(strN)
 
    # Check for all the left
    # rotations of the number
    for i in range(len(strN)):
 
        # If the number is prime, then
        # take the maximum among them
        if isPrime(int(temp)) and int(temp) > maxPrime:
            maxPrime = int(temp)
            cost = i
 
        # Left rotation
        temp = temp[1:]+temp[:1]
 
    optEle = maxPrime
 
    # If no prime number can be obtained
    if optEle == -1:
        optEle = float('inf')
        temp = str(strN)
 
        # Check all the left
        # rotations of the number
        for i in range(len(strN)):
 
            # Take the minimum element
            if int(temp) < optEle:
                optEle = int(temp)
                cost = i
 
            # Left rotation
            temp = temp[1:]+temp[:1]
        optEle *= (-1)
 
    return (optEle, cost)
 
# Function to find the maximum sum
# obtained using the given operations
def getMaxSum(arr):
 
    # Store the maximum sum and
    # the number of operations
    maxSum, cost = 0, 0
 
    # Traverse array elements
    for x in arr:
 
        # Get the optimal element and the
        # number of operations to obtain it
        optEle, optCost = rotateElement(x)
 
        # Increment the maximum difference
        # and number of operations required
        maxSum += optEle
        cost += optCost
 
    # Print the result
    print('Difference =', maxSum, ',',
          'Count of operations =', cost)
 
 
# Driver Code
 
arr = [541, 763, 321, 716, 143]
getMaxSum(arr)

// C# program for the above approach
using System;
using System.Collections.Generic;                   
 
class GFG {
 
  // Function to check if a
  // number is prime or not
  static 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
  static int[] rotateElement(int n)
  {
 
    // Convert the number to string
    string strN = n.ToString();
 
    // 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.Length; i++) {
 
      // If the number is prime, then
      // take the maximum among them
      if (isPrime(Int32.Parse(temp))
          &&  Int32.Parse(temp) > maxPrime) {
        maxPrime =  Int32.Parse(temp);
        cost = i;
      }
 
      // Left rotation
      temp = temp.Substring(1) + temp[0];
    }
 
    int optEle = maxPrime;
 
    // If no prime number can be obtained
    if (optEle == -1) {
      optEle = 2147483647;
      temp = strN;
 
      // Check all the left
      // rotations of the number
      for (int i = 0; i < strN.Length; i++) {
 
        // Take the minimum element
        if (Int32.Parse(temp) < optEle) {
          optEle = Int32.Parse(temp);
          cost = i;
        }
 
        // Left rotation
        temp = temp.Substring(1) + temp[0];
      }
      optEle *= (-1);
    }
    return new int[] { optEle, cost };
  }
 
  // Function to find the maximum sum
  // obtained using the given operations
  static void getMaxSum(int []arr)
  {
 
    // Store the maximum sum and
    // the number of operations
    int maxSum = 0, cost = 0;
 
    // Traverse array elements
    foreach (int x in arr) {
 
      // Get the optimal element and the
      // number of operations to obtain it
      int[] ret = rotateElement(x);
 
      int optEle = ret[0], optCost = ret[1];
 
      // Increment the maximum difference
      // and number of operations required
      maxSum += optEle;
      cost += optCost;
    }
 
    // Print the result
    Console.Write("Difference = " + maxSum + " , "+ "Count of operations = "
                  + cost);
  }
 
  // Driver Code
  public static void Main()
  {
 
    // Given array arr[]
    int []arr = { 541, 763, 321, 716, 143 };
 
    // Function call
    getMaxSum(arr);
  }
}
 
// This code is contributed by ipg2016107.

<script>
 
    // JavaScript program for the above approach
 
    // Function to check if a
    // number is prime or not
    function isPrime(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;
 
        let 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
    function rotateElement(n)
    {
 
        // Convert the number to string
        let strN = n.toString();
 
        // Stores the maximum prime number
        // that can be obtained from n
        let maxPrime = -1;
 
        // Store the required
        // number of operations
        let cost = 0;
 
        let temp = strN;
 
        // Check for all the left
        // rotations of the number
        for (let i = 0; i < strN.length; i++) {
 
            // If the number is prime, then
            // take the maximum among them
            if (isPrime(parseInt(temp)) && parseInt(temp) > maxPrime)
            {
                maxPrime = parseInt(temp);
                cost = i;
            }
 
            // Left rotation
            temp = temp.substr(1) + temp[0];
        }
 
        let optEle = maxPrime;
 
        // If no prime number can be obtained
        if (optEle == -1) {
            optEle = Number.MAX_VALUE;
            temp = strN;
 
            // Check all the left
            // rotations of the number
            for (let i = 0; i < strN.length; i++) {
 
                // Take the minimum element
                if (parseInt(temp) < optEle) {
                    optEle = parseInt(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
    function getMaxSum(arr,N)
    {
 
        // Store the maximum sum and
        // the number of operations
        let maxSum = 0, cost = 0;
 
        // Traverse array elements
        for (let i = 0; i < N; i++) {
            let x = arr[i];
 
            // Get the optimal element and the
            // number of operations to obtain it
            let ret = rotateElement(x);
 
            let optEle = ret[0], optCost = ret[1];
 
            // Increment the maximum difference
            // and number of operations required
            maxSum += optEle;
            cost += optCost;
        }
 
        // Print the result
         document.write("Difference = " + maxSum + " , "
            + "Count of operations = " + cost);
    }
 
    // Driven Program
 
    // Given array arr[]
    let arr = [ 541, 763, 321, 716, 143 ];
 
    // Store the size of the array
    let N = arr.length
 
    // Function call
    getMaxSum(arr, N);
 
</script>

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)