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++
// 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!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA