Dado un arreglo arr[] de N enteros positivos y un entero K , la tarea es encontrar el máximo de factores primos distintos en un subarreglo de longitud K .
Ejemplos:
Entrada: arr[] = {5, 9, 14, 6, 10, 77}, K=3
Salida: 5
Explicación:
El subarreglo de longitud 3 con factores primos distintos máximos es 6, 10, 77 y los factores primos son 2, 3, 5, 7, 11.Entrada: arr[] = {4, 2, 6, 10}, K=3
Salida: 3
Explicación:
El subarreglo de longitud 3 con un máximo de factores primos distintos es 2, 6, 10 y los factores primos son 2, 3, 5.
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles de longitud K y atravesar cada subarreglo y contar distintos factores primos de sus elementos. Finalmente, imprima el recuento máximo de factores primos distintos obtenidos para cualquier subarreglo. Complejidad temporal: O(N 2 log N)
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es utilizar la técnica de la ventana deslizante para resolver este problema. Siga los pasos a continuación:
- Genere y almacene el factor primo más pequeño de cada elemento usando Sieve .
- Almacene los distintos factores primos de los primeros elementos de la array K en un mapa .
- Atraviese el conjunto restante manteniendo la ventana de longitud K agregando el elemento actual al subarreglo anterior y eliminando el primer elemento del subarreglo anterior
- Encuentre todos los factores primos del elemento recién agregado al subarreglo y guárdelo en el Mapa . Reste la frecuencia de los factores primos del elemento eliminado del Mapa .
- Después de completar las operaciones anteriores para toda la array, imprima el tamaño de mapa máximo obtenido para cualquier subarreglo como respuesta.
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
// Stores smallest prime
// factor for every number
int spf[Max];
// Function to calculate smallest
// prime factor of every number
void sieve()
{
// Marking smallest prime factor
// of every number to itself
for (int i = 1; i < Max; i++)
spf[i] = i;
// Separately marking smallest prime
// factor of every even number to be 2
for (int i = 4; i < Max; i = i + 2)
spf[i] = 2;
for (int i = 3; i * i < Max; i++)
// If i is prime
if (spf[i] == i) {
// Mark spf for all numbers divisible by i
for (int j = i * i; j < Max; j = j + i) {
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find maximum distinct
// prime factors of subarray of length k
int maximumDPF(int arr[], int n, int k)
{
// Precalculate Smallest
// Prime Factors
sieve();
int ans = 0, num;
// Stores distinct prime factors
// for subarrays of size k
unordered_map<int, int> maps;
// Calculate total prime factors
// for first k array elements
for (int i = 0; i < k; i++) {
// Calculate prime factors of
// every element in O(logn)
num = arr[i];
while (num != 1) {
maps[spf[num]]++;
num = num / spf[num];
}
}
// Update maximum distinct
// prime factors obtained
ans = max((int)maps.size(), ans);
for (int i = k; i < n; i++) {
// Remove prime factors of
// the removed element
num = arr[i - k];
while (num != 1) {
// Reduce frequencies
// of prime factors
maps[spf[num]]--;
if (maps[spf[num]] == 0)
// Erase that index from map
maps.erase(spf[num]);
num = num / spf[num];
}
// Find prime factoes of
// added element
num = arr[i];
while (num != 1) {
// Increase frequencies
// of prime factors
maps[spf[num]]++;
num = num / spf[num];
}
// Update maximum distinct
// prime factors obtained
ans = max((int)maps.size(), ans);
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { 4, 2, 6, 10 };
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
cout << maximumDPF(arr, n, k) << endl;
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
static int Max = 100001;
static int spf[] = new int[Max];
// Function to precalculate smallest
// prime factor of every number
public static void sieve()
{
// Marking smallest prime factor
// of every number to itself.
for (int i = 1; i < Max; i++)
spf[i] = i;
// Separately marking smallest prime
// factor of every even number to be 2
for (int i = 4; i < Max; i = i + 2)
spf[i] = 2;
for (int i = 3; i * i < Max; i++)
// If i is prime
if (spf[i] == i) {
// Mark spf for all numbers divisible by i
for (int j = i * i; j < Max; j = j + i) {
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find maximum distinct
// prime factors of subarray of length k
public static int maximumDPF(int arr[], int n, int k)
{
// Precalculate smallest
// prime factor
sieve();
int ans = 0, num;
// Stores distinct prime factors
// for subarrays of size k
Map<Integer, Integer> maps
= new HashMap<Integer, Integer>();
// Calculate total prime factors
// for first k array elements
for (int i = 0; i < k; i++) {
// Calculate prime factors of
// every element in O(logn)
num = arr[i];
while (num != 1) {
maps.put(spf[num],
maps.getOrDefault(spf[num], 0)
+ 1);
num = num / spf[num];
}
}
// Update maximum distinct
// prime factors obtained
ans = Math.max((int)maps.size(), ans);
for (int i = k; i < n; i++) {
// Remove prime factors of
// the removed element
num = arr[i - k];
while (num != 1) {
// Reduce frequencies
// of prime factors
maps.put(spf[num],
maps.getOrDefault(spf[num], 0)
- 1);
if (maps.get(spf[num]) == 0)
maps.remove(spf[num]);
num = num / spf[num];
}
// Insert prime factors of
// the added element
num = arr[i];
while (num != 1) {
// Increase frequencies
// of prime factors
maps.put(spf[num],
maps.getOrDefault(spf[num], 0)
+ 1);
num = num / spf[num];
}
// Update maximum distinct
// prime factors obtained
ans = Math.max((int)maps.size(), ans);
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 2, 6, 10 };
int k = 3;
int n = arr.length;
System.out.println(maximumDPF(arr, n, k));
}
}
Python3
# Python program for the above approach
import math as mt
Max = 100001
# Stores smallest prime factor for
# every number
spf = [0 for i in range(Max)]
# Function to precalculate smallest
# prime factor of every number
def sieve():
# Marking smallest prime factor of every
# number to itself.
for i in range(1, Max):
spf[i] = i
# Separately marking spf for
# every even number as 2
for i in range(4, Max, 2):
spf[i] = 2
for i in range(3, mt.ceil(mt.sqrt(Max))):
# Checking if i is prime
if (spf[i] == i):
# marking SPF for all numbers
# divisible by i
for j in range(i * i, Max, i):
# marking spf[j] if it is
# not previously marked
if (spf[j] == j):
spf[j] = i
# Function to find maximum
# distinct prime factors
# of the subarray of length k
def maximumDPF(arr, n, k):
# precalculating Smallest Prime Factor
sieve()
ans = 0
# map to store distinct prime factor
# for subarray of size k
maps = {}
# Calculating the total prime factors
# for first k elements
for i in range(0, k):
# Calculating prime factors of
# every element in O(logn)
num = arr[i]
while num != 1:
maps[spf[num]] = maps.get(
spf[num], 0)+1
num = int(num / spf[num])
ans = max(len(maps), ans)
for i in range(k, n):
# Perform operation for
# removed element
num = arr[i - k]
while num != 1:
maps[spf[num]] = maps.get(
spf[num], 0)-1
# if value in map become 0,
# then erase that index from map
if maps.get(spf[num], 0) == 0:
maps.pop(spf[num])
num = int(num / spf[num])
# Perform operation for
# added element
num = arr[i]
while num != 1:
maps[spf[num]] = int(maps.get(
spf[num], 0))+1
num = int(num / spf[num])
ans = max(len(maps), ans)
return ans
# Driver Code
if __name__ == '__main__':
# Given array arr
arr = [4, 2, 6, 10]
# Given subarray size K
k = 3
n = len(arr)
# Function call
print(maximumDPF(arr, n, k))
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
public static int Max = 100001;
static int[] spf = new int[Max];
// Function to precalculate smallest
// prime factor of every number
public static void sieve()
{
// Marking smallest prime factor
// of every number to itself
for (int i = 1; i < Max; i++)
spf[i] = i;
// Marking smallest prime factor
// of every even number to be 2
for (int i = 4; i < Max; i = i + 2)
spf[i] = 2;
for (int i = 3; i * i < Max; i++)
// checking if i is prime
if (spf[i] == i) {
// Marking spf for all
// numbers divisible by i
for (int j = i * i; j < Max; j = j + i) {
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find maximum
// distinct prime factors
// of the subarray of length k
public static int maximumDPF(int[] arr,
int n, int k)
{
// precalculating Smallest Prime Factor
sieve();
int ans = 0, num, currentCount;
// Stores distinct prime factors
// for subarrays of size k
var maps = new Dictionary<int, int>();
// Calculating the total prime factors
// for first k array elements
for (int i = 0; i < k; i++) {
// Calculating prime factors of
// every element in O(logn)
num = arr[i];
while (num != 1) {
// Increase frequencies of
// prime factors
maps.TryGetValue(spf[num],
out currentCount);
maps[spf[num]] = currentCount + 1;
num = num / spf[num];
}
}
// Update maximum distinct
// prime factors obtained
ans = Math.Max(maps.Count, ans);
for (int i = k; i < n; i++) {
// Remove prime factors of
// removed element
num = arr[i - k];
while (num != 1) {
// Reduce frequencies
// of prime factors
maps.TryGetValue(spf[num],
out currentCount);
maps[spf[num]] = currentCount - 1;
if (maps[spf[num]] == 0)
// Erase that index from map
maps.Remove(spf[num]);
num = num / spf[num];
}
// Insert prime factors
// added element
num = arr[i];
while (num != 1) {
// Increase frequencies
// of prime factors
maps.TryGetValue(spf[num],
out currentCount);
maps[spf[num]] = currentCount + 1;
num = num / spf[num];
}
ans = Math.Max(maps.Count, ans);
}
// Update maximum distinct
// prime factors obtained
return ans;
}
// Driver code
static public void Main()
{
// Given array arr[]
int[] arr = { 4, 2, 6, 10 };
// Given subarray size K
int k = 3;
int n = arr.Length;
Console.Write(maximumDPF(arr, n, k));
}
}
Javascript
<script>
// JavaScript program for the above approach
const Max = 100001
// Stores smallest prime
// factor for every number
let spf = new Array(Max).fill(0);
// Function to calculate smallest
// prime factor of every number
const sieve = () => {
// Marking smallest prime factor
// of every number to itself
for (let i = 1; i < Max; i++)
spf[i] = i;
// Separately marking smallest prime
// factor of every even number to be 2
for (let i = 4; i < Max; i = i + 2)
spf[i] = 2;
for (let i = 3; i * i < Max; i++)
// If i is prime
if (spf[i] == i) {
// Mark spf for all numbers divisible by i
for (let j = i * i; j < Max; j = j + i) {
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find maximum distinct
// prime factors of subarray of length k
const maximumDPF = (arr, n, k) => {
// Precalculate Smallest
// Prime Factors
sieve();
let ans = 0, num;
// Stores distinct prime factors
// for subarrays of size k
let maps = {};
// Calculate total prime factors
// for first k array elements
for (let i = 0; i < k; i++) {
// Calculate prime factors of
// every element in O(logn)
num = arr[i];
while (num != 1) {
maps[spf[num]]++;
num = parseInt(num / spf[num]);
}
}
// Update maximum distinct
// prime factors obtained
ans = Math.max(Object.keys(maps).length, ans);
for (let i = k; i < n; i++) {
// Remove prime factors of
// the removed element
num = arr[i - k];
while (num != 1) {
// Reduce frequencies
// of prime factors
if (spf[num] in maps) maps[spf[num]]--;
if (maps[spf[num]] == 0)
// Erase that index from map
delete maps[spf[num]];
num = parseInt(num / spf[num]);
}
// Find prime factoes of
// added element
num = arr[i];
while (num != 1) {
// Increase frequencies
// of prime factors
maps[spf[num]] = spf[num] in maps ? maps[spf[num]] + 1 : 1;
num = parseInt(num / spf[num]);
}
// Update maximum distinct
// prime factors obtained
ans = Math.max(Object.keys(maps).length, ans);
}
return ans;
}
// Driver Code
let arr = [4, 2, 6, 10];
let k = 3;
let n = arr.length;
document.write(maximumDPF(arr, n, k));
// This code is contributed by rakeshsahni
</script>
Producción:
3
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por akhilsaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA