Given an array arr[] of size N, the task is to find the maximum difference between the sum of the prime numbers and the sum of the non-prime numbers present in the array, by left shifting the digits of array elements by 1 minimum number of times.
Examples:
Input: arr[] = {541, 763, 321, 716, 143}
Output: Difference = 631, Count of operations = 6
Explanation:
Operation 1: Left shift the digits of arr[1] (= 763). Therefore, arr[1] becomes 637.
Operation 2: Left shift the digits of arr[1] (= 637). Therefore, arr[1] becomes 376.
Operation 3: Left shift the digits of arr[2] (= 321). Therefore, arr[2] becomes 213.
Operation 4: Left shift the digits of arr[2] (= 213). Therefore, arr[2] becomes 132.
Operation 5: Left shift the digits of arr[3] (= 716). Therefore, arr[3] becomes 167.
Operation 6: Left shift the digits of arr[4] (= 143). Therefore, arr[4] becomes 431.
Therefore, Sum of prime array elements = 541 + 167 + 431 = 1139.
Therefore, sum of non-prime array elements = 376 + 132 = 508.
Therefore, difference = 1139 – 508 = 631.Input: {396, 361, 359, 496, 780}
Output: Difference = 236, Count of operations = 4
Explanation:
Operation 1: Left shift the digits of arr[1] (= 361). Therefore, arr[1] becomes 613.
Operation 2: Left shift the digits of arr[2] (= 359). Therefore, arr[2] becomes 593.
Operation 3: Left shift the digits of arr[4] (= 780). Therefore, arr[4] becomes 807.
Operation 4: Left shift the digits of arr[4] (= 807). Therefore, arr[4] becomes 078.
Therefore, required difference = 613 + 593 – 496 – 78 – 396 = 236.
Approach: The given problem can be solved greedily. If it is possible to convert an element into one or more than one prime number, then take the maximum of them. Otherwise, try to minimize the element by using all the possible rotations.
Follow the steps below to solve the problem:
- Initialize two variables, say ans and cost, to store the maximum difference and the minimum number of operations required respectively.
- Traverse the array arr[] using a variable i and perform the following steps:
- Initialize variables maxPrime and minRotation as -1 to store the maximum prime number and minimum number that can be obtained from arr[i] through left rotations.
- Generate all left rotations of the number arr[i].
- If arr[i] is a prime number exceeding maxPrime, then update maxPrime to arr[i] and the cost accordingly.
- If the value of maxPrime remains unchanged, find the value of minRotation by similarly generating all the left rotations.
- Add the value of arr[i] to ans.
- After completing the above steps, print the value of ans and cost as the result.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if a// number is prime or notbool 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 contributionpair<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 operationsvoid 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 Programint 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
// java program for the above approachimport 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); }} |
Python3
# Python program for the above approach# Function to check if a# number is prime or notdef 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 contributiondef 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 operationsdef 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 Codearr = [541, 763, 321, 716, 143]getMaxSum(arr) |
C#
// C# program for the above approachusing 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. |
Javascript
<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> |
Output:
Difference = 631 , Count of operations = 6
Time Complexity: O(X^2 * sqrt(X)), where n is the number of digits in the input number.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
