Dada una array arr[] que consta de N enteros positivos y un entero K , la tarea es encontrar la suma máxima de elementos de la array en una subarreglo que tenga la suma máxima de factores primos distintos en cada subarreglo de K longitud.
Nota: si hay varias respuestas, imprima la suma del subarreglo original que tenga la suma máxima.
Ejemplos:
Entrada: arr[] = {1, 4, 2, 10, 3}, K = 3
Salida: 16
Explicación:
Todos los posibles subarreglos de longitud 3 son:
{1, 4, 2} → teniendo 0+1+1= 2 factores primos distintos
{4, 2, 10} → teniendo 1+1+2= 4 factores primos distintos. Suma = 16.
{2, 10, 3} → teniendo 1+1+2= 4 factores primos distintos. Suma = 15.
Por lo tanto, la suma máxima de K subarreglos de longitud con un máximo de factores primos distintos es 16.Entrada: arr[] = {10, 14, 12, 9, 16, 11}, K = 2
Salida: 26
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles de longitud K a partir del arreglo dado y recorrer cada subarreglo y contar distintos factores primos de sus elementos y calcular sus sumas. Finalmente, imprima la suma máxima entre los subarreglos que tengan el recuento máximo de factores primos distintos.
Complejidad de tiempo: O(N 3 * sqrt(MAX)), donde MAX es el número máximo presente en la array.
Espacio auxiliar: O(N * sqrt(MAX))
Enfoque eficiente: la idea óptima es utilizar la técnica de la criba de Eratóstenes y la ventana deslizante para resolver este problema. Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos CountDsitinct[] , para almacenar el recuento de factores primos distintos hasta un límite usando tamiz incrementando el recuento de CountDistinct[] cada vez, mientras marca múltiplos de números primos como falsos .
- La suma de un subarreglo (o ventana) de tamaño K se puede obtener en tiempo constante usando la suma del subarreglo (o ventana) anterior de tamaño K usando la técnica de la ventana deslizante .
- Recorra la array arr[] y verifique qué subarreglo tiene la suma máxima de números primos distintos.
- Finalmente, imprima la suma del subarreglo o la suma del arreglo original que tiene el número máximo de factores primos.
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;
#define MAX 100001
// Function to print the sum of
// subarray of length K having
// maximum distinct prime factors
int maxSum(int arr[], int N, int K)
{
// If K exceeds N
if (N < K) {
cout << "Invalid";
return -1;
}
// Stores the count of distinct primes
int CountDistinct[MAX + 1];
// True, if index 'i' is a prime
bool prime[MAX + 1];
// Initialize the count of factors
// to 0 and set all indices as prime
for (int i = 0; i <= MAX; i++) {
CountDistinct[i] = 0;
prime[i] = true;
}
for (long long int i = 2; i <= MAX; i++) {
// If i is prime
if (prime[i] == true) {
// Number is prime
CountDistinct[i] = 1;
// Count of factors of a prime number is 1
for (long long int j = i * 2; j <= MAX;
j += i) {
// Increment CountDistinct as
// the factors of i
CountDistinct[j]++;
// Mark its multiple non-prime
prime[j] = false;
}
}
}
// Compute sum of first K-length subarray
int Maxarr_sum = 0, DistPrimeSum = 0;
for (int i = 0; i < K; i++) {
Maxarr_sum += arr[i];
DistPrimeSum += CountDistinct[arr[i]];
}
// Compute sums of remaining windows
// by removing first element of the
// previous window and adding last
// element of the current window
int curr_sum = DistPrimeSum;
int curr_arrSum = Maxarr_sum;
for (int i = K; i < N; i++) {
curr_sum += CountDistinct[arr[i]]
- CountDistinct[arr[i - K]];
curr_arrSum += arr[i] - arr[i - K];
if (curr_sum > DistPrimeSum) {
DistPrimeSum = curr_sum;
Maxarr_sum = curr_arrSum;
}
else if (curr_sum == DistPrimeSum) {
Maxarr_sum = max(
curr_arrSum, Maxarr_sum);
}
}
// Print the maximum sum
cout << Maxarr_sum;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 4, 2, 10, 3 };
// Given size of subarray
int K = 3;
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
maxSum(arr, N, K);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG
{
static int MAX = 100001;
// Function to print the sum of
// subarray of length K having
// maximum distinct prime factors
static void maxSum(int arr[], int N, int K)
{
// If K exceeds N
if (N < K) {
System.out.println("Invalid");
return;
}
// Stores the count of distinct primes
int CountDistinct[] = new int[MAX + 1];
// True, if index 'i' is a prime
boolean prime[] = new boolean[MAX + 1];
// Initialize the count of factors
// to 0 and set all indices as prime
for (int i = 0; i <= MAX; i++) {
CountDistinct[i] = 0;
prime[i] = true;
}
for (int i = 2; i <= MAX; i++) {
// If i is prime
if (prime[i] == true) {
// Number is prime
CountDistinct[i] = 1;
// Count of factors of a prime number is 1
for (int j = i * 2; j <= MAX; j += i) {
// Increment CountDistinct as
// the factors of i
CountDistinct[j]++;
// Mark its multiple non-prime
prime[j] = false;
}
}
}
// Compute sum of first K-length subarray
int Maxarr_sum = 0, DistPrimeSum = 0;
for (int i = 0; i < K; i++) {
Maxarr_sum += arr[i];
DistPrimeSum += CountDistinct[arr[i]];
}
// Compute sums of remaining windows
// by removing first element of the
// previous window and adding last
// element of the current window
int curr_sum = DistPrimeSum;
int curr_arrSum = Maxarr_sum;
for (int i = K; i < N; i++) {
curr_sum += CountDistinct[arr[i]]
- CountDistinct[arr[i - K]];
curr_arrSum += arr[i] - arr[i - K];
if (curr_sum > DistPrimeSum) {
DistPrimeSum = curr_sum;
Maxarr_sum = curr_arrSum;
}
else if (curr_sum == DistPrimeSum) {
Maxarr_sum
= Math.max(curr_arrSum, Maxarr_sum);
}
}
// Print the maximum sum
System.out.println(Maxarr_sum);
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 1, 4, 2, 10, 3 };
// Given size of subarray
int K = 3;
// Size of the array
int N = arr.length;
maxSum(arr, N, K);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach
import math
MAX = 100001
# Function to print the sum of
# subarray of length K having
# maximum distinct prime factors
def maxSum(arr, N, K):
# If K exceeds N
if (N < K):
print("Invalid")
return -1
# Stores the count of distinct primes
CountDistinct = [0]*(MAX + 1)
# True, if index 'i' is a prime
prime = [0]*(MAX + 1)
# Initialize the count of factors
# to 0 and set all indices as prime
for i in range(0,MAX+1):
CountDistinct[i] = 0
prime[i] = True
for i in range(2,MAX+1):
# If i is prime
if (prime[i] == True):
# Number is prime
CountDistinct[i] = 1
# Count of factors of a prime number is 1
for j in range(i * 2,MAX+1,i):
# Increment CountDistinct as
# the factors of i
CountDistinct[j] += 1
# Mark its multiple non-prime
prime[j] = False
# Compute sum of first K-length subarray
Maxarr_sum,DistPrimeSum = 0,0
for i in range(0,K):
Maxarr_sum += arr[i]
DistPrimeSum += CountDistinct[arr[i]]
# Compute sums of remaining windows
# by removing first element of the
# previous window and adding last
# element of the current window
curr_sum = DistPrimeSum
curr_arrSum = Maxarr_sum
for i in range(K,N):
curr_sum += CountDistinct[arr[i]]- CountDistinct[arr[i - K]]
curr_arrSum += arr[i] - arr[i - K]
if (curr_sum > DistPrimeSum):
DistPrimeSum = curr_sum
Maxarr_sum = curr_arrSum
elif (curr_sum == DistPrimeSum):
Maxarr_sum = max(curr_arrSum, Maxarr_sum)
print(Maxarr_sum)
# Driver Code
# Given array
arr = [ 1, 4, 2, 10, 3 ]
# Given size of subarray
K = 3
# Size of the array
N = len(arr)
maxSum(arr, N, K)
# This code is contributed by shinjanpatra
C#
// C# Program to implement
// the above approach
using System;
public class GFG
{
static int MAX = 100001;
// Function to print the sum of
// subarray of length K having
// maximum distinct prime factors
static void maxSum(int []arr, int N, int K)
{
// If K exceeds N
if (N < K) {
Console.WriteLine("Invalid");
return;
}
// Stores the count of distinct primes
int []CountDistinct = new int[MAX + 1];
// True, if index 'i' is a prime
bool []prime = new bool[MAX + 1];
// Initialize the count of factors
// to 0 and set all indices as prime
for (int i = 0; i <= MAX; i++) {
CountDistinct[i] = 0;
prime[i] = true;
}
for (int i = 2; i <= MAX; i++) {
// If i is prime
if (prime[i] == true) {
// Number is prime
CountDistinct[i] = 1;
// Count of factors of a prime number is 1
for (int j = i * 2; j <= MAX; j += i) {
// Increment CountDistinct as
// the factors of i
CountDistinct[j]++;
// Mark its multiple non-prime
prime[j] = false;
}
}
}
// Compute sum of first K-length subarray
int Maxarr_sum = 0, DistPrimeSum = 0;
for (int i = 0; i < K; i++) {
Maxarr_sum += arr[i];
DistPrimeSum += CountDistinct[arr[i]];
}
// Compute sums of remaining windows
// by removing first element of the
// previous window and adding last
// element of the current window
int curr_sum = DistPrimeSum;
int curr_arrSum = Maxarr_sum;
for (int i = K; i < N; i++) {
curr_sum += CountDistinct[arr[i]]
- CountDistinct[arr[i - K]];
curr_arrSum += arr[i] - arr[i - K];
if (curr_sum > DistPrimeSum) {
DistPrimeSum = curr_sum;
Maxarr_sum = curr_arrSum;
}
else if (curr_sum == DistPrimeSum) {
Maxarr_sum
= Math.Max(curr_arrSum, Maxarr_sum);
}
}
// Print the maximum sum
Console.WriteLine(Maxarr_sum);
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 1, 4, 2, 10, 3 };
// Given size of subarray
int K = 3;
// Size of the array
int N = arr.Length;
maxSum(arr, N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
let MAX = 100001
// Function to print the sum of
// subarray of length K having
// maximum distinct prime factors
function maxSum(arr, N, K)
{
// If K exceeds N
if (N < K) {
document.write("Invalid");
return -1;
}
// Stores the count of distinct primes
let CountDistinct = new Array(MAX + 1);
// True, if index 'i' is a prime
let prime = new Array(MAX + 1);
// Initialize the count of factors
// to 0 and set all indices as prime
for (let i = 0; i <= MAX; i++) {
CountDistinct[i] = 0;
prime[i] = true;
}
for (let i = 2; i <= MAX; i++) {
// If i is prime
if (prime[i] == true) {
// Number is prime
CountDistinct[i] = 1;
// Count of factors of a prime number is 1
for (let j = i * 2; j <= MAX;
j += i) {
// Increment CountDistinct as
// the factors of i
CountDistinct[j]++;
// Mark its multiple non-prime
prime[j] = false;
}
}
}
// Compute sum of first K-length subarray
let Maxarr_sum = 0, DistPrimeSum = 0;
for (let i = 0; i < K; i++) {
Maxarr_sum += arr[i];
DistPrimeSum += CountDistinct[arr[i]];
}
// Compute sums of remaining windows
// by removing first element of the
// previous window and adding last
// element of the current window
let curr_sum = DistPrimeSum;
let curr_arrSum = Maxarr_sum;
for (let i = K; i < N; i++) {
curr_sum += CountDistinct[arr[i]]
- CountDistinct[arr[i - K]];
curr_arrSum += arr[i] - arr[i - K];
if (curr_sum > DistPrimeSum) {
DistPrimeSum = curr_sum;
Maxarr_sum = curr_arrSum;
}
else if (curr_sum == DistPrimeSum) {
Maxarr_sum = Math.max(curr_arrSum, Maxarr_sum);
}
}
// Print the maximum sum
document.write(Maxarr_sum);
}
// Driver Code
// Given array
let arr = [ 1, 4, 2, 10, 3 ];
// Given size of subarray
let K = 3;
// Size of the array
let N = arr.length
maxSum(arr, N, K);
</script>
Producción
16
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sourav2901 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA