Encuentre el elemento de la array que tiene el mismo número de números primos a la izquierda y a la derecha

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *