Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar un índice de la array que tenga el mismo número de números primos presentes a la izquierda y a la derecha.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 7, 5, 10, 1, 8}
Salida: 2
Explicación:
Considere el índice 2, luego los números primos a su izquierda son {2, 3} y los números primos a su derecha están {7, 5}.
Como, el conteo de números primos al índice izquierdo y derecho es 2, que es igual. Por lo tanto, imprime 2.Entrada: arr[] = {8, 10, 2, 7, 3}
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es contar los números primos a la izquierda y a la derecha de cada elemento de la array atravesando la array e imprimir el índice en el que se encuentra que el recuento de números primos es igual.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando la técnica de la criba de Eratóstenes y la suma de prefijos para prealmacenar los números primos a la izquierda y a la derecha en un elemento de array. Siga los pasos a continuación para resolver el problema:
- Primero, encuentra el valor máximo de la array arr[] y guárdalo en una variable, digamos maxValue .
- Inicialice un mapa < int, int> , digamos St , para almacenar todos los números primos en él.
- Iterar sobre el rango [2, maxValue] y empujar todos los valores en St .
- Itere sobre el rango [2, maxValue] y realice las siguientes operaciones:
- Inicialice una variable j como 1 e itere mientras i*j sea menor o igual que maxValue .
- En cada iteración de los pasos anteriores, elimine i*j de St e incremente j en 1 .
- Inicialice dos variables, digamos LeftCount y RightCount , para almacenar el recuento de números primos en una array de prefijos y en una array de sufijos, respectivamente.
- Inicialice dos arrays, digamos Prefix[] y Suffix[] , para almacenar la array de suma de prefijos y la array de suma de sufijos del recuento de números primos de la array arr[] .
- Recorra la array arr[] y realice las siguientes operaciones:
- Asigne LeftCount a Prefix[i] .
- Si el valor de arr[i] está presente en St , aumente el valor de LeftCount en 1 .
- Iterar sobre el rango [0, N-1] en sentido inverso y realizar las siguientes operaciones:
- Asigne RightCount a Sufijo[i] .
- Si arr[i] está presente en St , aumente el valor de RightCount en 1 .
- Itere sobre el rango [0, N – 1] y si el valor de Prefix[i] es igual al valor de Suffix[i] , imprima el índice i como la respuesta y salga del ciclo .
- Después de completar los pasos anteriores, si ninguno de los casos anteriores satisface, imprima -1 .
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 find the index of the
// array such that the count of prime
// numbers to its either ends are same
int findIndex(int arr[], int N)
{
// Store the maximum value in
// the array
int maxValue = INT_MIN;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
maxValue = max(maxValue, arr[i]);
}
// Stores all the numbers
map<int, int> St;
// Iterate over the range [1, Max]
for (int i = 1; i <= maxValue; i++) {
// Increment the value of st[i]
St[i]++;
}
// Removes 1 from the map St
if (St.find(1) != St.end()) {
St.erase(1);
}
// Perform Sieve of Prime Numbers
for (int i = 2;
i <= sqrt(maxValue); i++) {
int j = 2;
// While i*j is less than
// the maxValue
while ((i * j) <= maxValue) {
// If i*j is in map St
if (St.find(i * j)
!= St.end()) {
// Erase the value (i * j)
St.erase(i * j);
}
// Increment the value of j
j++;
}
}
// Stores the count of prime from
// index 0 to i
int LeftCount = 0;
// Stores the count of prime numbers
int Prefix[N];
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
Prefix[i] = LeftCount;
// If arr[i] is present in the
// map st
if (St.find(arr[i])
!= St.end()) {
LeftCount++;
}
}
// Stores the count of prime from
// index i to N-1
int RightCount = 0;
// Stores the count of prime numbers
int Suffix[N];
// Iterate over the range [0, N-1]
// in reverse order
for (int i = N - 1; i >= 0; i--) {
Suffix[i] = RightCount;
// If arr[i] is in map st
if (St.find(arr[i])
!= St.end()) {
RightCount++;
}
}
// Iterate over the range [0, N-1]
for (int i = 0; i < N; i++) {
// If prefix[i] is equal
// to the Suffix[i]
if (Prefix[i] == Suffix[i]) {
return i;
}
}
// Return -1 if no such index
// is present
return -1;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 7, 5, 10, 1, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findIndex(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.HashMap;
public class GFG
{
// Function to find the index of the
// array such that the count of prime
// numbers to its either ends are same
static int findIndex(int arr[], int N)
{
// Store the maximum value in
// the array
int maxValue = Integer.MIN_VALUE;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
maxValue = Math.max(maxValue, arr[i]);
}
// Stores all the numbers
HashMap<Integer, Integer> St = new HashMap<>();
// Iterate over the range [1, Max]
for (int i = 1; i <= maxValue; i++) {
// Increment the value of st[i]
St.put(i, St.getOrDefault(i, 0) + 1);
}
// Removes 1 from the map St
if (St.containsKey(1)) {
St.remove(1);
}
// Perform Sieve of Prime Numbers
for (int i = 2; i <= Math.sqrt(maxValue); i++) {
int j = 2;
// While i*j is less than
// the maxValue
while ((i * j) <= maxValue) {
// If i*j is in map St
if (St.containsKey(i * j)) {
// Erase the value (i * j)
St.remove(i * j);
}
// Increment the value of j
j++;
}
}
// Stores the count of prime from
// index 0 to i
int LeftCount = 0;
// Stores the count of prime numbers
int Prefix[] = new int[N];
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
Prefix[i] = LeftCount;
// If arr[i] is present in the
// map st
if (St.containsKey(arr[i])) {
LeftCount++;
}
}
// Stores the count of prime from
// index i to N-1
int RightCount = 0;
// Stores the count of prime numbers
int Suffix[] = new int[N];
// Iterate over the range [0, N-1]
// in reverse order
for (int i = N - 1; i >= 0; i--) {
Suffix[i] = RightCount;
// If arr[i] is in map st
if (St.containsKey(arr[i])) {
RightCount++;
}
}
// Iterate over the range [0, N-1]
for (int i = 0; i < N; i++) {
// If prefix[i] is equal
// to the Suffix[i]
if (Prefix[i] == Suffix[i]) {
return i;
}
}
// Return -1 if no such index
// is present
return -1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 7, 5, 10, 1, 8 };
int N = arr.length;
System.out.println(findIndex(arr, N));
}
}
// This code is contributed by abhinavjain194
Python3
# Python 3 program for the above approach from collections import defaultdict import sys import math # Function to find the index of the # array such that the count of prime # numbers to its either ends are same def findIndex(arr, N): # Store the maximum value in # the array maxValue = -sys.maxsize - 1 # Traverse the array arr[] for i in range(N): maxValue = max(maxValue, arr[i]) # / Stores all the numbers St = defaultdict(int) # Iterate over the range [1, Max] for i in range(1, maxValue + 1): # Increment the value of st[i] St[i] += 1 # Removes 1 from the map St if (1 in St): St.pop(1) # Perform Sieve of Prime Numbers for i in range(2, int(math.sqrt(maxValue)) + 1): j = 2 # While i*j is less than # the maxValue while ((i * j) <= maxValue): # If i*j is in map St if (i * j) in St: # Erase the value (i * j) St.pop(i * j) # Increment the value of j j += 1 # Stores the count of prime from # index 0 to i LeftCount = 0 # Stores the count of prime numbers Prefix = [0] * N # Traverse the array arr[] for i in range(N): Prefix[i] = LeftCount # If arr[i] is present in the # map st if (arr[i] in St): LeftCount += 1 # Stores the count of prime from # index i to N-1 RightCount = 0 # Stores the count of prime numbers Suffix = [0] * N # Iterate over the range [0, N-1] # in reverse order for i in range(N - 1, -1, -1): Suffix[i] = RightCount # If arr[i] is in map st if arr[i] in St: RightCount += 1 # Iterate over the range [0, N-1] for i in range(N): # If prefix[i] is equal # to the Suffix[i] if (Prefix[i] == Suffix[i]): return i # Return -1 if no such index # is present return -1 # Driver Code if __name__ == "__main__": arr = [2, 3, 4, 7, 5, 10, 1, 8] N = len(arr) print(findIndex(arr, N)) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the index of the
// array such that the count of prime
// numbers to its either ends are same
static int findIndex(int[] arr, int N)
{
// Store the maximum value in
// the array
int maxValue = Int32.MinValue;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
maxValue = Math.Max(maxValue, arr[i]);
}
// Stores all the numbers
Dictionary<int,int> St = new Dictionary<int,int>();
// Iterate over the range [1, Max]
for (int i = 1; i <= maxValue; i++) {
// Increment the value of st[i]
St.Add(i, 1);
}
// Removes 1 from the map St
if (St.ContainsKey(1)) {
St.Remove(1);
}
// Perform Sieve of Prime Numbers
for (int i = 2; i <= Math.Sqrt(maxValue); i++) {
int j = 2;
// While i*j is less than
// the maxValue
while ((i * j) <= maxValue) {
// If i*j is in map St
if (St.ContainsKey(i * j)) {
// Erase the value (i * j)
St.Remove(i * j);
}
// Increment the value of j
j++;
}
}
// Stores the count of prime from
// index 0 to i
int LeftCount = 0;
// Stores the count of prime numbers
int[] Prefix = new int[N];
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
Prefix[i] = LeftCount;
// If arr[i] is present in the
// map st
if (St.ContainsKey(arr[i])) {
LeftCount++;
}
}
// Stores the count of prime from
// index i to N-1
int RightCount = 0;
// Stores the count of prime numbers
int[] Suffix = new int[N];
// Iterate over the range [0, N-1]
// in reverse order
for (int i = N - 1; i >= 0; i--) {
Suffix[i] = RightCount;
// If arr[i] is in map st
if (St.ContainsKey(arr[i])) {
RightCount++;
}
}
// Iterate over the range [0, N-1]
for (int i = 0; i < N; i++) {
// If prefix[i] is equal
// to the Suffix[i]
if (Prefix[i] == Suffix[i]) {
return i;
}
}
// Return -1 if no such index
// is present
return -1;
}
// Driver code
static public void Main (){
int[] arr = { 2, 3, 4, 7, 5, 10, 1, 8 };
int N = arr.Length;
Console.WriteLine(findIndex(arr, N));
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// JavaScript program to count frequencies of array items
// Function to find the index of the
// array such that the count of prime
// numbers to its either ends are same
function findIndex( arr, N)
{
// Store the maximum value in
// the array
let maxValue = Number.MIN_VALUE;
;
// Traverse the array arr[]
for (let i = 0; i < N; i++)
{
maxValue = Math.max(maxValue, arr[i]);
}
// Stores all the numbers
var St = new Map();
// Iterate over the range [1, Max]
for (let i = 1; i <= maxValue; i++) {
// Increment the value of st[i]
St.set(i, 1);
}
// Removes 1 from the map St
if (St.has(1)) {
St.delete(1);
}
// Perform Sieve of Prime Numbers
for (let i = 2; i <= Math.sqrt(maxValue); i++) {
let j = 2;
// While i*j is less than
// the maxValue
while ((i * j) <= maxValue) {
// If i*j is in map St
if (St.has(i * j)) {
// Erase the value (i * j)
St.delete(i * j);
}
// Increment the value of j
j++;
}
}
// Stores the count of prime from
// index 0 to i
let LeftCount = 0;
// Stores the count of prime numbers
let Prefix = new Array(N);
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
Prefix[i] = LeftCount;
// If arr[i] is present in the
// map st
if (St.has(arr[i])) {
LeftCount++;
}
}
// Stores the count of prime from
// index i to N-1
let RightCount = 0;
// Stores the count of prime numbers
let Suffix = new Array(N);
// Iterate over the range [0, N-1]
// in reverse order
for (let i = N - 1; i >= 0; i--) {
Suffix[i] = RightCount;
// If arr[i] is in map st
if (St.has(arr[i])) {
RightCount++;
}
}
// Iterate over the range [0, N-1]
for (let i = 0; i < N; i++) {
// If prefix[i] is equal
// to the Suffix[i]
if (Prefix[i] == Suffix[i]) {
return i;
}
}
// Return -1 if no such index
// is present
return -1;
}
// Driver Code
let arr = [ 2, 3, 4, 7, 5, 10, 1, 8 ];
let N = arr.length;
document.write(findIndex(arr, N));
// This code is contributed by jana_sayantan.
</script>
Producción:
2
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por supratik_mitra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA