Dada una array A[] de tamaño N , la tarea de cada elemento de la array es contar los elementos de la array a su derecha que son más pequeños que él y son primos .
Ejemplos:
Entrada: N = 10, A[] = {5, 5, 17, 9, 12, 15, 11, 7, 39, 3} Salida: 2 1 3 2 3 3 2 1 1 0
Explicación :
Para
i = 1, los elementos en j = [2, 10] son una respuesta válida.
Para i = 2, los elementos en j = [10] son una respuesta válida.
Para i = 3, los elementos en j = [7, 8, 10] son una respuesta válida.
Para i = 4, los elementos en j = [8, 10] son una respuesta válida.
Para i = 5, los elementos en j = [7, 8, 10] son una respuesta válida.
Para i = 6, los elementos en j = [7, 8, 10] son una respuesta válida.
Para i = 7, los elementos en j = [8, 10] son una respuesta válida.
Para i = 8, los elementos en j = [10] son una respuesta válida.
Para i = 9, los elementos en j = [10] son una respuesta válida.
Para i = 5, ningún elemento está a su derecha.Entrada: N = 6, A[] = {43, 3, 5, 7, 2, 41}
Salida: 5 1 1 1 0 0
Explicación:
Para i = 1, elementos en j = [2, 3, 4, 5 , 6] son una respuesta válida.
Para i = 2, los elementos en j = [5] son una respuesta válida.
Para i = 3, los elementos en j = [5] son una respuesta válida.
Para i = 4, los elementos en j = [5] son una respuesta válida.
Para i = 5, no hay respuesta válida.
Para i = 6, no hay respuesta válida.
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y, para cada elemento, A[i] , iterar sobre todos los elementos a su derecha y contar la cantidad de elementos menores que A[i] y primos .
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 check if a
// number is prime or not
bool is_prime(int n)
{
if (n <= 1)
return 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
// Function to find the count of
// smaller primes on the right
// of each array element
void countSmallerPrimes(int ar[], int N)
{
for (int i = 0; i < N; i++) {
// Stores the count of
// smaller primes
int count = 0;
for (int j = i + 1; j < N; j++) {
// If A[j] <= A[i] and A[j] is prime
if (ar[j] <= ar[i] && is_prime(ar[j])) {
// Increase count
count++;
}
}
// Print the count for
// the current element
cout << count << " ";
}
}
// Driver Code
int main()
{
int ar[] = { 43, 3, 5, 7, 2, 41 };
int N = sizeof ar / sizeof ar[0];
// Function call
countSmallerPrimes(ar, N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check if a
// number is prime or not
static boolean is_prime(int n)
{
if (n <= 1)
return false;
for(int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
// Function to find the count of
// smaller primes on the right
// of each array element
static void countSmallerPrimes(int ar[], int N)
{
for(int i = 0; i < N; i++)
{
// Stores the count of
// smaller primes
int count = 0;
for(int j = i + 1; j < N; j++)
{
// If A[j] <= A[i] and A[j] is prime
if (ar[j] <= ar[i] && is_prime(ar[j]))
{
// Increase count
count++;
}
}
// Print the count for
// the current element
System.out.print(count + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int ar[] = { 43, 3, 5, 7, 2, 41 };
int N = ar.length;
// Function call
countSmallerPrimes(ar, N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function to check if a # number is prime or not def is_prime(n): if (n <= 1): return 0 for i in range(2, n + 1): if i * i > n: break if (n % i == 0): return 0 return 1 # Function to find the count of # smaller primes on the right # of each array element def countSmallerPrimes(ar, N): for i in range(N): # Stores the count of # smaller primes count = 0 for j in range(i + 1, N): # If A[j] <= A[i] and A[j] is prime if (ar[j] <= ar[i] and is_prime(ar[j])): # Increase count count += 1 # Print the count for # the current element print(count, end = " ") # Driver Code if __name__ == '__main__': ar = [ 43, 3, 5, 7, 2, 41 ] N = len(ar) # Function call countSmallerPrimes(ar, N) # This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
class GFG{
// Function to check if a
// number is prime or not
static bool is_prime(int n)
{
if (n <= 1)
return false;
for (int i = 2;
i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
// Function to find the count of
// smaller primes on the right
// of each array element
static void countSmallerPrimes(int[] ar,
int N)
{
for (int i = 0; i < N; i++)
{
// Stores the count of
// smaller primes
int count = 0;
for (int j = i + 1; j < N; j++)
{
// If A[j] <= A[i]
// and A[j] is prime
if (ar[j] <= ar[i] &&
is_prime(ar[j]))
{
// Increase count
count++;
}
}
// Print the count for
// the current element
Console.Write(count + " ");
}
}
// Driver Code
public static void Main()
{
int[] ar = {43, 3, 5,
7, 2, 41};
int N = ar.Length;
// Function call
countSmallerPrimes(ar, N);
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check if a
// number is prime or not
function is_prime(n)
{
if (n <= 1)
return false;
for(let i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
// Function to find the count of
// smaller primes on the right
// of each array element
function countSmallerPrimes(ar, N)
{
for(let i = 0; i < N; i++)
{
// Stores the count of
// smaller primes
let count = 0;
for(let j = i + 1; j < N; j++)
{
// If A[j] <= A[i] and A[j] is prime
if (ar[j] <= ar[i] && is_prime(ar[j]))
{
// Increase count
count++;
}
}
// Print the count for
// the current element
document.write(count + " ");
}
}
// Driver Code
let ar = [ 43, 3, 5, 7, 2, 41 ];
let N = ar.length;
// Function call
countSmallerPrimes(ar, N);
</script>
Producción
5 1 1 1 0 0
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es observar que el enfoque anterior se puede optimizar iterando sobre la array de derecha a izquierda y calculando el recuento requerido de números primos para cada elemento de la array utilizando Fenwick Tree . Siga los pasos a continuación para resolver el problema:
- Recorra la array de derecha a izquierda y calcule la cantidad de números primos más pequeños a la derecha del elemento de la array actual mediante getSum() . Imprime el conteo obtenido.
- Ahora, verifique si el elemento de array actual es principal o no y actualice el árbol de Fenwick en consecuencia.
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;
const int maxn = 1e6 + 5;
int BITree[maxn];
// Function to check if a
// number is prime or not
bool is_prime(int n)
{
if (n <= 1)
return 0;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return 0;
return 1;
}
// Function to update a Binary Tree
void update_bitree(int BITree[],
int index, int value)
{
while (index <= maxn) {
BITree[index] += value;
index += (index & (-index));
}
}
// Function to find the sum of
// all the elements which are
// less than or equal to index
int sum_bitree(int BITree[], int index)
{
int s = 0;
while (index > 0) {
s += BITree[index];
index -= (index & (-index));
}
return s;
}
// Function to find the number
// of smaller primes on the right
// for every array element
void countSmallerPrimes(int BITree[],
int ar[], int N)
{
int ans[N];
// Iterate the array in backwards
for (int i = N - 1; i >= 0; i--) {
// Calculating the required
// number of primes
ans[i] = sum_bitree(BITree, ar[i]);
// If current array
// element is prime
if (is_prime(ar[i]))
// Update the Fenwick tree
update_bitree(BITree, ar[i], 1);
}
for (int i = 0; i < N; i++)
cout << ans[i] << " ";
}
// Driver Code
int main()
{
int ar[] = { 5, 5, 17, 9, 12,
15, 11, 7, 39, 3 };
int N = sizeof ar / sizeof ar[0];
// Function call
countSmallerPrimes(BITree, ar, N);
return 0;
}
Java
// Java Program for the
// above approach
//include "bits/stdJava.h"
import java.util.*;
class GFG{
static int maxn =
(int)1e6 + 5;
static int []BITree =
new int[maxn];
// Function to check if a
// number is prime or not
static boolean is_prime(int n)
{
if (n <= 1)
return false;
for (int i = 2;
i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to update a Binary Tree
static void update_bitree(int BITree[],
int index,
int value)
{
while (index <= maxn)
{
BITree[index] += value;
index += (index & (-index));
}
}
// Function to find the sum of
// all the elements which are
// less than or equal to index
static int sum_bitree(int BITree[],
int index)
{
int s = 0;
while (index > 0)
{
s += BITree[index];
index -= (index & (-index));
}
return s;
}
// Function to find the number
// of smaller primes on the right
// for every array element
static void countSmallerPrimes(int BITree[],
int ar[], int N)
{
int []ans = new int[N];
// Iterate the array in backwards
for (int i = N - 1; i >= 0; i--)
{
// Calculating the required
// number of primes
ans[i] = sum_bitree(BITree,
ar[i]);
// If current array
// element is prime
if (is_prime(ar[i]))
// Update the Fenwick tree
update_bitree(BITree,
ar[i], 1);
}
for (int i = 0; i < N; i++)
System.out.print(ans[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
int ar[] = {5, 5, 17, 9, 12,
15, 11, 7, 39, 3};
int N = ar.length;
// Function call
countSmallerPrimes(BITree, ar, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the # above approach # include "bits/stdPython.h" maxn = int(1e6) + 5 BITree = [0] * (maxn) # Function to check if a # number is prime or not def is_prime(n): if (n <= 1): return False i = 2 while (i * i <= n): if (n % i == 0): return False i += 1 return True # Function to update a Binary Tree def update_bitree(index, value): while (index <= maxn): BITree[index] += value index += (index & (-index)) # Function to find the sum of # all the elements which are # less than or equal to index def sum_bitree(index): s = 0 while (index > 0): s += BITree[index] index -= (index & (-index)) return s # Function to find the number # of smaller primes on the right # for every array element def countSmallerPrimes(ar, N): ans = [0] * (N) global BITree # Iterate the array in backwards for i in range(N - 1, 0, -1): # Calculating the required # number of primes ans[i] = sum_bitree(ar[i]) # If current array # element is prime if (is_prime(ar[i])): # Update the Fenwick tree update_bitree(ar[i], 1) ans[0] = 2 for i in range(N): print(ans[i], end = " ") # Driver Code if __name__ == '__main__': ar = [ 5, 5, 17, 9, 12, 15, 11, 7, 39, 3 ] N = len(ar) # Function call countSmallerPrimes(ar, N) # This code is contributed by Amit Katiyar
C#
// C# Program for the
// above approach
//include "bits/stdJava.h"
using System;
class GFG{
static int maxn =
(int)1e6 + 5;
static int []BITree =
new int[maxn];
// Function to check if a
// number is prime or not
static bool is_prime(int n)
{
if (n <= 1)
return false;
for (int i = 2;
i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to update a Binary Tree
static void update_bitree(int []BITree,
int index,
int value)
{
while (index <= maxn)
{
BITree[index] += value;
index += (index & (-index));
}
}
// Function to find the sum of
// all the elements which are
// less than or equal to index
static int sum_bitree(int []BITree,
int index)
{
int s = 0;
while (index > 0)
{
s += BITree[index];
index -= (index & (-index));
}
return s;
}
// Function to find the number
// of smaller primes on the right
// for every array element
static void countSmallerPrimes(int []BITree,
int []ar, int N)
{
int []ans = new int[N];
// Iterate the array in backwards
for (int i = N - 1; i >= 0; i--)
{
// Calculating the required
// number of primes
ans[i] = sum_bitree(BITree,
ar[i]);
// If current array
// element is prime
if (is_prime(ar[i]))
// Update the Fenwick tree
update_bitree(BITree,
ar[i], 1);
}
for (int i = 0; i < N; i++)
Console.Write(ans[i] + " ");
}
// Driver Code
public static void Main(String[] args)
{
int []ar = {5, 5, 17, 9, 12,
15, 11, 7, 39, 3};
int N = ar.Length;
// Function call
countSmallerPrimes(BITree, ar, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript Program for the above approach
let maxn = 1e6 + 5;
let BITree = new Array(maxn);
BITree.fill(0);
// Function to check if a
// number is prime or not
function is_prime(n)
{
if (n <= 1)
return false;
for (let i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to update a Binary Tree
function update_bitree(BITree, index, value)
{
while (index <= maxn)
{
BITree[index] += value;
index += (index & (-index));
}
}
// Function to find the sum of
// all the elements which are
// less than or equal to index
function sum_bitree(BITree, index)
{
let s = 0;
while (index > 0)
{
s += BITree[index];
index -= (index & (-index));
}
return s;
}
// Function to find the number
// of smaller primes on the right
// for every array element
function countSmallerPrimes(BITree, ar, N)
{
let ans = new Array(N);
// Iterate the array in backwards
for (let i = N - 1; i >= 0; i--)
{
// Calculating the required
// number of primes
ans[i] = sum_bitree(BITree, ar[i]);
// If current array
// element is prime
if (is_prime(ar[i]))
// Update the Fenwick tree
update_bitree(BITree, ar[i], 1);
}
for (let i = 0; i < N; i++)
document.write(ans[i] + " ");
}
let ar = [5, 5, 17, 9, 12, 15, 11, 7, 39, 3];
let N = ar.length;
// Function call
countSmallerPrimes(BITree, ar, N);
</script>
Producción
2 1 3 2 3 3 2 1 1 0
Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dbarnwal888 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA