Dada una array arr[] de tamaño N , la tarea es contar el número de pares de la array dada cuyo producto contiene solo un único factor primo distinto.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 4
Explicación:
Los pares que tienen un solo factor primo distinto en su producto son los siguientes:
arr[0] * arr[1] = (1 * 2) = 2 Por lo tanto, el único factor primo distinto es 2.
arr[0] * arr[2] = (1 * 3) = 3. Por lo tanto, el único factor primo distinto es 3.
arr[0] * arr[3] = ( 1 * 4) = 2 2 Por lo tanto, el único factor primo distinto es 2.
arr[1] * arr[3] = (2 * 4) = 8 2 3 Por lo tanto, el único factor primo distinto es 2.
Por lo tanto, el la salida es 4Entrada: arr[] = {2, 4, 6, 8}
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y generar todos los pares posibles de la array y, para cada par, verificar si el producto de los elementos contiene solo un factor primo distinto o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo.
Complejidad temporal: O(N 2 * √X), donde X es el producto máximo posible de un par en el arreglo dado.
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar Hashing . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntof1 para almacenar el recuento de elementos de array cuyo valor es 1 .
- Cree un mapa , digamos mp para almacenar el recuento de elementos de array que contiene solo un factor primo distinto .
- Recorra la array y, para cada elemento de la array, verifique si el recuento de factores primos distintos es 1 o no. Si se determina que es cierto, inserte el elemento actual en mp .
- Inicialice una variable, digamos res , para almacenar el recuento de pares cuyo producto de elementos contiene solo un único factor primo distinto.
- Recorra el mapa y actualice la res += cntof1 * (X) + (X *(X- 1)) / 2 . Donde X almacena el conteo del elemento de array que contiene solo un único factor primo distinto i .
- Finalmente, imprima el valor de res .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find a single
// distinct prime factor of N
int singlePrimeFactor(int N)
{
// Stores distinct
// prime factors of N
unordered_set<int>
disPrimeFact;
// Calculate prime factor of N
for (int i = 2; i * i <= N; ++i) {
// Calculate distinct
// prime factor
while (N % i == 0) {
// Insert i into
// disPrimeFact
disPrimeFact.insert(i);
// Update N
N /= i;
}
}
// If N is not equal to 1
if (N != 1)
{
// Insert N into
// disPrimeFact
disPrimeFact.insert(N);
}
// If N contains a single
// distinct prime factor
if (disPrimeFact.size() == 1) {
// Return single distinct
// prime factor of N
return *disPrimeFact.begin();
}
// If N contains more than one
// distinct prime factor
return -1;
}
// Function to count pairs in the array
// whose product contains only
// single distinct prime factor
int cntsingleFactorPair(int arr[], int N)
{
// Stores count of 1s
// in the array
int countOf1 = 0;
// mp[i]: Stores count of array elements
// whose distinct prime factor is only i
unordered_map<int, int> mp;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// If current element is 1
if(arr[i] == 1)
{
countOf1++;
continue;
}
// Store distinct
// prime factor of arr[i]
int factorValue
= singlePrimeFactor(arr[i]);
// If arr[i] contains more
// than one prime factor
if (factorValue == -1) {
continue;
}
// If arr[i] contains
// a single prime factor
else {
mp[factorValue]++;
}
}
// Stores the count of pairs whose
// product of elements contains only
// a single distinct prime factor
int res = 0;
// Traverse the map mp[]
for (auto it : mp) {
// Stores count of array elements
// whose prime factor is (it.first)
int X = it.second;
// Update res
res += countOf1 * X +
(X * (X - 1) ) / 2;
}
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << cntsingleFactorPair(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find a single
// distinct prime factor of N
static int singlePrimeFactor(int N)
{
// Stores distinct
// prime factors of N
HashSet<Integer> disPrimeFact =
new HashSet<>();
// Calculate prime factor of N
for (int i = 2;
i * i <= N; ++i)
{
// Calculate distinct
// prime factor
while (N % i == 0)
{
// Insert i into
// disPrimeFact
disPrimeFact.add(i);
// Update N
N /= i;
}
}
// If N is not equal to 1
if (N != 1)
{
// Insert N into
// disPrimeFact
disPrimeFact.add(N);
}
// If N contains a single
// distinct prime factor
if (disPrimeFact.size() == 1)
{
// Return single distinct
// prime factor of N
for(int i : disPrimeFact)
return i;
}
// If N contains more than
// one distinct prime factor
return -1;
}
// Function to count pairs in
// the array whose product
// contains only single distinct
// prime factor
static int cntsingleFactorPair(int arr[],
int N)
{
// Stores count of 1s
// in the array
int countOf1 = 0;
// mp[i]: Stores count of array
// elements whose distinct prime
// factor is only i
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// If current element is 1
if(arr[i] == 1)
{
countOf1++;
continue;
}
// Store distinct
// prime factor of arr[i]
int factorValue =
singlePrimeFactor(arr[i]);
// If arr[i] contains more
// than one prime factor
if (factorValue == -1)
{
continue;
}
// If arr[i] contains
// a single prime factor
else
{
if(mp.containsKey(factorValue))
mp.put(factorValue,
mp.get(factorValue) + 1);
else
mp.put(factorValue, 1);
}
}
// Stores the count of pairs whose
// product of elements contains only
// a single distinct prime factor
int res = 0;
// Traverse the map mp[]
for (Map.Entry<Integer,
Integer> it :
mp.entrySet())
{
// Stores count of array
// elements whose prime
// factor is (it.first)
int X = it.getValue();
// Update res
res += countOf1 * X +
(X * (X - 1) ) / 2;
}
return res;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4};
int N = arr.length;
System.out.print(
cntsingleFactorPair(arr, N));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to implement
# the above approach
# Function to find a single
# distinct prime factor of N
def singlePrimeFactor(N):
# Stores distinct
# prime factors of N
disPrimeFact = {}
# Calculate prime factor of N
for i in range(2, N + 1):
if i * i > N:
break
# Calculate distinct
# prime factor
while (N % i == 0):
# Insert i into
# disPrimeFact
disPrimeFact[i] = 1
# Update N
N //= i
# If N is not equal to 1
if (N != 1):
# Insert N into
# disPrimeFact
disPrimeFact[N] = 1
# If N contains a single
# distinct prime factor
if (len(disPrimeFact) == 1):
# Return single distinct
# prime factor of N
return list(disPrimeFact.keys())[0]
# If N contains more than one
# distinct prime factor
return -1
# Function to count pairs in the array
# whose product contains only
# single distinct prime factor
def cntsingleFactorPair(arr, N):
# Stores count of 1s
# in the array
countOf1 = 0
# mp[i]: Stores count of array elements
# whose distinct prime factor is only i
mp = {}
# Traverse the array arr[]
for i in range(N):
# If current element is 1
if (arr[i] == 1):
countOf1 += 1
continue
# Store distinct
# prime factor of arr[i]
factorValue = singlePrimeFactor(arr[i])
# If arr[i] contains more
# than one prime factor
if (factorValue == -1):
continue
# If arr[i] contains
# a single prime factor
else:
mp[factorValue] = mp.get(factorValue, 0) + 1
# Stores the count of pairs whose
# product of elements contains only
# a single distinct prime factor
res = 0
# Traverse the map mp[]
for it in mp:
# Stores count of array elements
# whose prime factor is (it.first)
X = mp[it]
# Update res
res += countOf1 * X + (X * (X - 1) ) // 2
return res
# Driver Code
if __name__ == '__main__':
arr = [ 1, 2, 3, 4 ]
N = len(arr)
print(cntsingleFactorPair(arr, N))
# This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find a single
// distinct prime factor of N
static int singlePrimeFactor(int N)
{
// Stores distinct
// prime factors of N
HashSet<int> disPrimeFact =
new HashSet<int>();
// Calculate prime factor of N
for (int i = 2;
i * i <= N; ++i)
{
// Calculate distinct
// prime factor
while (N % i == 0)
{
// Insert i into
// disPrimeFact
disPrimeFact.Add(i);
// Update N
N /= i;
}
}
// If N is not equal to 1
if(N != 1)
{
// Insert N into
// disPrimeFact
disPrimeFact.Add(N);
}
// If N contains a single
// distinct prime factor
if (disPrimeFact.Count == 1)
{
// Return single distinct
// prime factor of N
foreach(int i in disPrimeFact)
return i;
}
// If N contains more than
// one distinct prime factor
return -1;
}
// Function to count pairs in
// the array whose product
// contains only single distinct
// prime factor
static int cntsingleFactorPair(int []arr,
int N)
{
// Stores count of 1s
// in the array
int countOf1 = 0;
// mp[i]: Stores count of array
// elements whose distinct prime
// factor is only i
Dictionary<int,
int> mp =
new Dictionary<int,
int>();
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// If current element is 1
if(arr[i] == 1)
{
countOf1++;
continue;
}
// Store distinct
// prime factor of arr[i]
int factorValue =
singlePrimeFactor(arr[i]);
// If arr[i] contains more
// than one prime factor
if (factorValue == -1)
{
continue;
}
// If arr[i] contains
// a single prime factor
else
{
if(mp.ContainsKey(factorValue))
mp[factorValue] = mp[factorValue] + 1;
else
mp.Add(factorValue, 1);
}
}
// Stores the count of pairs whose
// product of elements contains only
// a single distinct prime factor
int res = 0;
// Traverse the map mp[]
foreach(KeyValuePair<int,
int> ele1 in mp)
{
// Stores count of array
// elements whose prime
// factor is (it.first)
int X = ele1.Value;
// Update res
res += countOf1 * X +
(X * (X - 1) ) / 2;
}
return res;
}
// Driver Code
public static void Main()
{
int []arr = {1, 2, 3, 4};
int N = arr.Length;
Console.WriteLine(
cntsingleFactorPair(arr, N));
}
}
// This code is contributed by bgangwar59
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find a single
// distinct prime factor of N
function singlePrimeFactor(N)
{
// Stores distinct
// prime factors of N
var disPrimeFact = {};
// Calculate prime factor of N
for(var i = 2; i * i <= N; ++i)
{
// Calculate distinct
// prime factor
while (N % i === 0)
{
// Insert i into
// disPrimeFact
disPrimeFact[i] = 1;
// Update N
N = parseInt(N / i);
}
}
// If N is not equal to 1
if (N !== 1)
{
// Insert N into
// disPrimeFact
disPrimeFact[N] = 1;
}
// If N contains a single
// distinct prime factor
if (Object.keys(disPrimeFact).length === 1)
{
// Return single distinct
// prime factor of N
for(const [key, value] of Object.entries(
disPrimeFact))
{
return key;
}
}
// If N contains more than
// one distinct prime factor
return -1;
}
// Function to count pairs in
// the array whose product
// contains only single distinct
// prime factor
function cntsingleFactorPair(arr, N)
{
// Stores count of 1s
// in the array
var countOf1 = 0;
// mp[i]: Stores count of array
// elements whose distinct prime
// factor is only i
var mp = {};
// Traverse the array arr[]
for(var i = 0; i < N; i++)
{
// If current element is 1
if (arr[i] === 1)
{
countOf1++;
continue;
}
// Store distinct
// prime factor of arr[i]
var factorValue = singlePrimeFactor(arr[i]);
// If arr[i] contains more
// than one prime factor
if (factorValue === -1)
{
continue;
}
// If arr[i] contains
// a single prime factor
else
{
if (mp.hasOwnProperty(factorValue))
mp[factorValue] = mp[factorValue] + 1;
else
mp[factorValue] = 1;
}
}
// Stores the count of pairs whose
// product of elements contains only
// a single distinct prime factor
var res = 0;
// Traverse the map mp[]
for(const [key, value] of Object.entries(mp))
{
// Stores count of array
// elements whose prime
// factor is (it.first)
var X = value;
// Update res
res = parseInt(res + countOf1 * X +
(X * (X - 1)) / 2);
}
return res;
}
// Driver Code
var arr = [ 1, 2, 3, 4 ];
var N = arr.length;
document.write(cntsingleFactorPair(arr, N));
// This code is contributed by rdtank
</script>
Producción:
4
Complejidad de tiempo: O(N√X) , donde X es el elemento máximo de la array dada.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA