Dada una array ‘arr’ de longitud ‘n’. La tarea es encontrar el subarreglo contiguo más grande que tenga un recuento de números primos estrictamente mayor que el recuento de números no primos.
Ejemplos :
Input: arr[] = {4, 7, 4, 7, 11, 5, 4, 4, 4, 5}
Output: 9
Input: arr[] = { 1, 9, 3, 4, 5, 6, 7, 8 }
Output: 5
Enfoque: para encontrar el subarreglo más grande en el que el recuento de primos es estrictamente mayor que el recuento de no primos: en
primer lugar, use la criba para encontrar el número primo.
Reemplace todos los primos con 1 en la array y todos los no primos con -1. Ahora, este problema es similar al subarreglo más largo que tiene una cuenta de 1 más que una cuenta de 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
bool prime[1000000 + 5];
void findPrime()
{
memset(prime, true, sizeof(prime));
prime[1] = false;
for (int p = 2; p * p <= 1000000; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= 1000000; i += p)
prime[i] = false;
}
}
}
// Function to find the length of longest
// subarray having count of primes more
// than count of non-primes
int lenOfLongSubarr(int arr[], int n)
{
// unordered_map 'um' implemented as
// hash table
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// consider -1 as non primes and 1 as primes
sum += prime[arr[i]] == 0 ? -1 : 1;
// when subarray starts form index '0'
if (sum == 1)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
else if (um.find(sum) == um.end())
um[sum] = i;
// check if 'sum-1' is present in 'um'
// or not
if (um.find(sum - 1) != um.end()) {
// update maxLength
if (maxLen < (i - um[sum - 1]))
maxLen = i - um[sum - 1];
}
}
// required maximum length
return maxLen;
}
// Driver code
int main()
{
findPrime();
int arr[] = { 1, 9, 3, 4, 5, 6, 7, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << lenOfLongSubarr(arr, n) << endl;
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
class GfG {
static boolean prime[] = new boolean[1000000 + 5];
static void findPrime()
{
Arrays.fill(prime, true);
prime[1] = false;
for (int p = 2; p * p <= 1000000; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= 1000000; i += p)
prime[i] = false;
}
}
}
// Function to find the length of longest
// subarray having count of primes more
// than count of non-primes
static int lenOfLongSubarr(int arr[], int n)
{
// unordered_map 'um' implemented as
// hash table
Map<Integer, Integer> um = new HashMap<Integer, Integer>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// consider -1 as non primes and 1 as primes
sum += prime[arr[i]] == false ? -1 : 1;
// when subarray starts form index '0'
if (sum == 1)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
else if (!um.containsKey(sum))
um.put(sum, i);
// check if 'sum-1' is present in 'um'
// or not
if (um.containsKey(sum - 1)) {
// update maxLength
if (maxLen < (i - um.get(sum - 1)))
maxLen = i - um.get(sum - 1);
}
}
// required maximum length
return maxLen;
}
// Driver code
public static void main(String[] args)
{
findPrime();
int arr[] = { 1, 9, 3, 4, 5, 6, 7, 8 };
int n = arr.length;
System.out.println(lenOfLongSubarr(arr, n));
}
}
Python3
# Python3 implementation of above approach
prime = [True] * (1000000 + 5)
def findPrime():
prime[0], prime[1] = False, False
for p in range(2, 1001):
# If prime[p] is not changed,
# then it is a prime
if prime[p] == True:
# Update all multiples of p
for i in range(p * 2, 1000001, p):
prime[i] = False
# Function to find the length of longest
# subarray having count of primes more
# than count of non-primes
def lenOfLongSubarr(arr, n):
# unordered_map 'um' implemented as
# hash table
um = {}
Sum, maxLen = 0, 0
# traverse the given array
for i in range(0, n):
# consider -1 as non primes and 1 as primes
Sum = Sum-1 if prime[arr[i]] == False else Sum + 1
# when subarray starts form index '0'
if Sum == 1:
maxLen = i + 1
# make an entry for 'sum' if
# it is not present in 'um'
elif Sum not in um:
um[Sum] = i
# check if 'sum-1' is present
# in 'um' or not
if (Sum - 1) in um:
# update maxLength
if maxLen < (i - um[Sum - 1]):
maxLen = i - um[Sum - 1]
# required maximum length
return maxLen
# Driver Code
if __name__ == "__main__":
findPrime()
arr = [1, 9, 3, 4, 5, 6, 7, 8]
n = len(arr)
print(lenOfLongSubarr(arr, n))
# This code is contributed
# by Rituraj Jain
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GfG {
static bool[] prime = new bool[1000000 + 5];
static void findPrime()
{
Array.Fill(prime, true);
prime[1] = false;
for (int p = 2; p * p <= 1000000; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= 1000000; i += p)
prime[i] = false;
}
}
}
// Function to find the length of longest
// subarray having count of primes more
// than count of non-primes
static int lenOfLongSubarr(int[] arr, int n)
{
// unordered_map 'um' implemented as
// hash table
Dictionary<int, int> um = new Dictionary<int, int>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// consider -1 as non primes and 1 as primes
sum += prime[arr[i]] == false ? -1 : 1;
// when subarray starts form index '0'
if (sum == 1)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
else if (!um.ContainsKey(sum))
um[sum] = i;
// check if 'sum-1' is present in 'um'
// or not
if (um.ContainsKey(sum - 1)) {
// update maxLength
if (maxLen < (i - um[sum - 1]))
maxLen = i - um[sum - 1];
}
}
// required maximum length
return maxLen;
}
// Driver code
public static void Main()
{
findPrime();
int[] arr = { 1, 9, 3, 4, 5, 6, 7, 8 };
int n = arr.Length;
Console.WriteLine(lenOfLongSubarr(arr, n));
}
}
// This code is contributed by Code_Mech.
Javascript
<script>
// Javascript implementation of above approach
let prime = new Array(1000000 + 5);
function findPrime() {
prime.fill(true)
prime[1] = false;
for (let p = 2; p * p <= 1000000; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (let i = p * 2; i <= 1000000; i += p)
prime[i] = false;
}
}
}
// Function to find the length of longest
// subarray having count of primes more
// than count of non-primes
function lenOfLongSubarr(arr, n) {
// unordered_map 'um' implemented as
// hash table
let um = new Map();
let sum = 0, maxLen = 0;
// traverse the given array
for (let i = 0; i < n; i++) {
// consider -1 as non primes and 1 as primes
sum += prime[arr[i]] == 0 ? -1 : 1;
// when subarray starts form index '0'
if (sum == 1)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
else if (!um.has(sum))
um.set(sum, i);
// check if 'sum-1' is present in 'um'
// or not
if (um.has(sum - 1)) {
// update maxLength
if (maxLen < (i - um.get(sum - 1)))
maxLen = i - um.get(sum - 1);
}
}
// required maximum length
return maxLen;
}
// Driver code
findPrime();
let arr = [1, 9, 3, 4, 5, 6, 7, 8];
let n = arr.length;
document.write(lenOfLongSubarr(arr, n) + "<br>")
// This code is contributed by Saurabh Jaiswal
</script>
Producción:
5