Dada una array arr[] de tamaño N , la tarea es encontrar el índice en la array dada donde la suma de los números primos presentes a su izquierda es igual a la suma de los números primos presentes a su derecha.
Ejemplos:
Entrada: arr[] = {11, 4, 7, 6, 13, 1, 5}
Salida: 3
Explicación: Suma de números primos a la izquierda del índice 3 = 11 + 7 = 18
Suma de números primos a la derecha del índice 3 = 13 + 5 = 18Entrada: arr[] = {5, 2, 1, 7}
Salida: 2
Explicación: Suma de números primos a la izquierda del índice 2 = 5 + 2 = 7
Suma de números primos a la derecha del índice 2 = 7
Enfoque ingenuo: el enfoque más simple es recorrer la array y verificar la condición dada para cada índice en el rango [0, N – 1] . Si se determina que la condición es verdadera para cualquier índice, imprima el valor de ese índice.
Complejidad de tiempo: O(N 2 *√M), donde M es el elemento más grande de la array
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 la suma de 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:
- Recorra la array para encontrar el valor máximo presente en la array .
- Utilice la criba de Eratóstenes para averiguar los números primos que son menores o iguales que el valor máximo presente en la array. Guarda estos elementos en un Mapa .
- Inicialice una array, digamos first_array . Recorra la array y almacene la suma de todos los números primos hasta el i -ésimo índice en first_array[i] .
- Inicialice una array, digamos second_array . Recorra la array en sentido inverso y almacene la suma de todos los elementos hasta el i -ésimo índice en second_array[i] .
- Recorra las arrays first_array y second_array y verifique si en algún índice, ambos valores son iguales o no. Si se encuentra que es cierto, devuelve ese índice.
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 an index in the
// array having sum of prime numbers
// to its left and right equal
int find_index(int arr[], int N)
{
// Stores the maximum value
// present in the array
int max_value = INT_MIN;
for (int i = 0; i < N; i++) {
max_value = max(max_value, arr[i]);
}
// Stores all positive
// elements which are <= max_value
map<int, int> store;
for (int i = 1; i <= max_value; i++) {
store[i]++;
}
// If 1 is present
if (store.find(1) != store.end()) {
// Remove 1
store.erase(1);
}
// Sieve of Eratosthenes to
// store all prime numbers which
// are <= max_value in the Map
for (int i = 2; i <= sqrt(max_value); i++) {
int multiple = 2;
// Erase non-prime numbers
while ((i * multiple) <= max_value) {
if (store.find(i * multiple) != store.end()) {
store.erase(i * multiple);
}
multiple++;
}
}
// Stores the sum of
// prime numbers from left
int prime_sum_from_left = 0;
// Stores the sum of prime numbers
// to the left of each index
int first_array[N];
for (int i = 0; i < N; i++) {
// Stores the sum of prime numbers
// to the left of the current index
first_array[i] = prime_sum_from_left;
if (store.find(arr[i]) != store.end()) {
// Add current value to
// the prime sum if the
// current value is prime
prime_sum_from_left += arr[i];
}
}
// Stores the sum of
// prime numbers from right
int prime_sum_from_right = 0;
// Stores the sum of prime numbers
// to the right of each index
int second_array[N];
for (int i = N - 1; i >= 0; i--) {
// Stores the sum of prime
// numbers to the right of
// the current index
second_array[i] = prime_sum_from_right;
if (store.find(arr[i]) != store.end()) {
// Add current value to the
// prime sum if the
// current value is prime
prime_sum_from_right += arr[i];
}
}
// Traverse through the two
// arrays to find the index
for (int i = 0; i < N; i++) {
// Compare the values present
// at the current index
if (first_array[i] == second_array[i]) {
// Return the index where
// both the values are same
return i;
}
}
// No index is found.
return -1;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 11, 4, 7, 6, 13, 1, 5 };
// Size of Array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << find_index(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
// Function to find an index in the
// array having sum of prime numbers
// to its left and right equal
static int find_index(int arr[], int N)
{
// Stores the maximum value
// present in the array
int max_value = Integer.MIN_VALUE;
for(int i = 0; i < N; i++)
{
max_value = Math.max(max_value, arr[i]);
}
// Stores all positive
// elements which are <= max_value
Map<Integer, Integer> store= new HashMap<>();
for(int i = 1; i <= max_value; i++)
{
store.put(i, store.getOrDefault(i, 0) + 1);
}
// If 1 is present
if (store.containsKey(1))
{
// Remove 1
store.remove(1);
}
// Sieve of Eratosthenes to
// store all prime numbers which
// are <= max_value in the Map
for(int i = 2; i <= Math.sqrt(max_value); i++)
{
int multiple = 2;
// Erase non-prime numbers
while ((i * multiple) <= max_value)
{
if (store.containsKey(i * multiple))
{
store.remove(i * multiple);
}
multiple++;
}
}
// Stores the sum of
// prime numbers from left
int prime_sum_from_left = 0;
// Stores the sum of prime numbers
// to the left of each index
int[] first_array = new int[N];
for(int i = 0; i < N; i++)
{
// Stores the sum of prime numbers
// to the left of the current index
first_array[i] = prime_sum_from_left;
if (store.containsKey(arr[i]))
{
// Add current value to
// the prime sum if the
// current value is prime
prime_sum_from_left += arr[i];
}
}
// Stores the sum of
// prime numbers from right
int prime_sum_from_right = 0;
// Stores the sum of prime numbers
// to the right of each index
int[] second_array= new int[N];
for(int i = N - 1; i >= 0; i--)
{
// Stores the sum of prime
// numbers to the right of
// the current index
second_array[i] = prime_sum_from_right;
if (store.containsKey(arr[i]))
{
// Add current value to the
// prime sum if the
// current value is prime
prime_sum_from_right += arr[i];
}
}
// Traverse through the two
// arrays to find the index
for(int i = 0; i < N; i++)
{
// Compare the values present
// at the current index
if (first_array[i] == second_array[i])
{
// Return the index where
// both the values are same
return i;
}
}
// No index is found.
return -1;
}
// Driver code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 11, 4, 7, 6, 13, 1, 5 };
// Size of Array
int N = arr.length;
// Function Call
System.out.println(find_index(arr, N));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
from math import sqrt
# Function to find an index in the
# array having sum of prime numbers
# to its left and right equal
def find_index(arr, N):
# Stores the maximum value
# present in the array
max_value = -10**9
for i in range(N):
max_value = max(max_value, arr[i])
# Stores all positive
# elements which are <= max_value
store = {}
for i in range(1, max_value + 1):
store[i] = store.get(i, 0) + 1
# If 1 is present
if (1 in store):
# Remove 1
del store[1]
# Sieve of Eratosthenes to
# store all prime numbers which
# are <= max_value in the Map
for i in range(2, int(sqrt(max_value)) + 1):
multiple = 2
# Erase non-prime numbers
while ((i * multiple) <= max_value):
if (i * multiple in store):
del store[i * multiple]
multiple += 1
# Stores the sum of
# prime numbers from left
prime_sum_from_left = 0
# Stores the sum of prime numbers
# to the left of each index
first_array = [0]*N
for i in range(N):
# Stores the sum of prime numbers
# to the left of the current index
first_array[i] = prime_sum_from_left
if arr[i] in store:
# Add current value to
# the prime sum if the
# current value is prime
prime_sum_from_left += arr[i]
# Stores the sum of
# prime numbers from right
prime_sum_from_right = 0
# Stores the sum of prime numbers
# to the right of each index
second_array = [0]*N
for i in range(N - 1, -1, -1):
# Stores the sum of prime
# numbers to the right of
# the current index
second_array[i] = prime_sum_from_right
if (arr[i] in store):
# Add current value to the
# prime sum if the
# current value is prime
prime_sum_from_right += arr[i]
# Traverse through the two
# arrays to find the index
for i in range(N):
# Compare the values present
# at the current index
if (first_array[i] == second_array[i]):
# Return the index where
# both the values are same
return i
# No index is found.
return -1
# Driver Code
if __name__ == '__main__':
# Given array arr[]
arr= [11, 4, 7, 6, 13, 1, 5]
# Size of Array
N = len(arr)
# Function Call
print (find_index(arr, N))
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find an index in the
// array having sum of prime numbers
// to its left and right equal
static int find_index(int[] arr, int N)
{
// Stores the maximum value
// present in the array
int max_value = Int32.MinValue;
for(int i = 0; i < N; i++)
{
max_value = Math.Max(max_value, arr[i]);
}
// Stores all positive
// elements which are <= max_value
Dictionary<int,
int> store = new Dictionary<int,
int>();
for(int i = 1; i <= max_value; i++)
{
if (!store.ContainsKey(i))
store[i] = 0;
store[i]++;
}
// If 1 is present
if (store.ContainsKey(1))
{
// Remove 1
store.Remove(1);
}
// Sieve of Eratosthenes to
// store all prime numbers which
// are <= max_value in the Map
for(int i = 2; i <= Math.Sqrt(max_value); i++)
{
int multiple = 2;
// Erase non-prime numbers
while ((i * multiple) <= max_value)
{
if (store.ContainsKey(i * multiple))
{
store.Remove(i * multiple);
}
multiple++;
}
}
// Stores the sum of
// prime numbers from left
int prime_sum_from_left = 0;
// Stores the sum of prime numbers
// to the left of each index
int[] first_array = new int[N];
for(int i = 0; i < N; i++)
{
// Stores the sum of prime numbers
// to the left of the current index
first_array[i] = prime_sum_from_left;
if (store.ContainsKey(arr[i]))
{
// Add current value to
// the prime sum if the
// current value is prime
prime_sum_from_left += arr[i];
}
}
// Stores the sum of
// prime numbers from right
int prime_sum_from_right = 0;
// Stores the sum of prime numbers
// to the right of each index
int[] second_array = new int[N];
for(int i = N - 1; i >= 0; i--)
{
// Stores the sum of prime
// numbers to the right of
// the current index
second_array[i] = prime_sum_from_right;
if (store.ContainsKey(arr[i]))
{
// Add current value to the
// prime sum if the
// current value is prime
prime_sum_from_right += arr[i];
}
}
// Traverse through the two
// arrays to find the index
for(int i = 0; i < N; i++)
{
// Compare the values present
// at the current index
if (first_array[i] == second_array[i])
{
// Return the index where
// both the values are same
return i;
}
}
// No index is found.
return -1;
}
// Driver Code
public static void Main()
{
// Given array arr[]
int[] arr = { 11, 4, 7, 6, 13, 1, 5 };
// Size of Array
int N = arr.Length;
// Function Call
Console.WriteLine(find_index(arr, N));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to find an index in the
// array having sum of prime numbers
// to its left and right equal
function find_index(arr,N)
{
// Stores the maximum value
// present in the array
let max_value = Number.MIN_VALUE;
for (let i = 0; i < N; i++) {
max_value = Math.max(max_value, arr[i]);
}
// Stores all positive
// elements which are <= max_value
let store=new Map();
for (let i = 1; i <= max_value; i++) {
if(!store.has(i))
store.set(i,0);
store.set(i,store.get(i)+1);
}
// If 1 is present
if (store.has(1)) {
// Remove 1
store.delete(1);
}
// Sieve of Eratosthenes to
// store all prime numbers which
// are <= max_value in the Map
for (let i = 2; i <= Math.sqrt(max_value); i++) {
let multiple = 2;
// Erase non-prime numbers
while ((i * multiple) <= max_value) {
if (store.has(i * multiple)) {
store.delete(i * multiple);
}
multiple++;
}
}
// Stores the sum of
// prime numbers from left
let prime_sum_from_left = 0;
// Stores the sum of prime numbers
// to the left of each index
let first_array=new Array(N);
for (let i = 0; i < N; i++) {
// Stores the sum of prime numbers
// to the left of the current index
first_array[i] = prime_sum_from_left;
if (store.has(arr[i])) {
// Add current value to
// the prime sum if the
// current value is prime
prime_sum_from_left += arr[i];
}
}
// Stores the sum of
// prime numbers from right
let prime_sum_from_right = 0;
// Stores the sum of prime numbers
// to the right of each index
let second_array=new Array(N);
for (let i = N - 1; i >= 0; i--) {
// Stores the sum of prime
// numbers to the right of
// the current index
second_array[i] = prime_sum_from_right;
if (store.has(arr[i]) ) {
// Add current value to the
// prime sum if the
// current value is prime
prime_sum_from_right += arr[i];
}
}
// Traverse through the two
// arrays to find the index
for (let i = 0; i < N; i++) {
// Compare the values present
// at the current index
if (first_array[i] == second_array[i]) {
// Return the index where
// both the values are same
return i;
}
}
// No index is found.
return -1;
}
// Driver Code
// Given array arr[]
let arr=[11, 4, 7, 6, 13, 1, 5];
// Size of Array
let N=arr.length;
// Function Call
document.write(find_index(arr, N));
// This code is contributed by patel2127
</script>
Producción:
3
Complejidad de tiempo: O(N + max(arr[])loglog(max(arr[]))
Espacio auxiliar: O(max(arr[]) + 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