Prerrequisitos: Factorización prima usando Sieve
Dados dos arreglos arr1[] y arr2[] de tamaño M y N con elementos distintos en cada uno de los arreglos, la tarea es encontrar ese par de elementos (uno del primer arreglo y otro del segundo array) cuyo producto es un cuadrado perfecto. Imprime -1 si no se pueden formar parejas.
Ejemplos:
Entrada: arr1[] = {1, 8, 6, 9}, arr2[] = {2, 24, 49}
Salida: (1, 49), (8, 2), (6, 24), (9, 49)
Explicación:
El producto de pares en la salida son todos cuadrados perfectos.
Par 1: 1 x 49 = 49
Par 2: 8 x 2 = 16
Par 3: 6 x 24 = 144
Par 4: 9 x 49 = 441Entrada: arr1[] = {2, 3, 4}, arr2[] = {9, 5}
Salida: -1
Enfoque ingenuo: El enfoque ingenuo consiste en elegir todos los pares posibles y comprobar si forman un cuadrado perfecto. Esto se puede hacer en tiempo cuadrático.
Complejidad de tiempo: O(M*N)
Enfoque Eficiente: La idea es utilizar el concepto de factorización prima. Analicemos cómo usar el concepto en este problema.
Los siguientes son los escenarios donde el producto de dos números forman un cuadrado perfecto:
- Si ambos números son cuadrados perfectos, su producto siempre forma un cuadrado perfecto.
- Si uno de los números no es un cuadrado perfecto, su producto nunca puede ser un cuadrado perfecto.
- En caso de que ambos números sean cuadrados no perfectos, entonces el número de factores primos de ambos números combinados debe ser par.
- Por ejemplo,
sea x = 6, y = 1176
descomposición en factores primos de x = 2 x 3 (2 y 3 ocurren en momentos impares)
factorización en primos de y = 2 x 2 x 2 x 3 x 7 x 7 (2 y 3 ocurren en momentos impares)
x * y = 7056 que es el cuadrado de 84
- Dado que x e y tienen todos los tiempos impares que ocurren primos, pero x * y tiene un número par de factores primos. Por lo tanto, formarán un cuadrado perfecto.
Por lo tanto, la array arr1[] se recorre y para cada elemento en arr1[] , los números en la array arr2[] que tienen el mismo producto de primos que ocurren en tiempos impares que el elemento actual. Esto se puede hacer usando map STL en C++ en tiempo de inicio de sesión .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print pairs whose
// product is a perfect square
#include <bits/stdc++.h>
using namespace std;
// Maximum number upto which sieve is performed
#define MAXN 100001
// Array to perform Sieve of Eratosthenes
// and store prime numbers
int spf[MAXN];
// Function to perform sieve of
// eratosthenes on the array spf.
void sieve()
{
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
spf[i] = i;
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (spf[i] == i) {
for (int j = i * i; j < MAXN; j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to return the product of the
// odd occurring prime factors of a number
int getProductOddOccuringPrimes(int x)
{
// Product of 1 with perfect square gives
// perfect square, 1 is returned for x = 1
if (x == 1)
return 1;
// Temporary container of prime factors
vector<int> ret;
while (x != 1) {
ret.push_back(spf[x]);
x = x / spf[x];
}
// ans contains the product of primes
// which occurs odd number of times
int count = 1, ans = 1;
for (int i = 0, j = 1; j < ret.size(); ++j, ++i) {
if (ret[i] != ret[j]) {
if (count & 1)
ans *= ret[i];
count = 0;
}
count++;
}
// Checks if count is odd or not
if (count & 1)
ans *= ret[ret.size() - 1];
return ans;
}
// Function to print the pairs whose product is
// a perfect square
void printPairs(int n, int m, int a[], int b[])
{
int countPairs = 0;
// For storing the indices with same
// product of odd times occurring Primes as key
map<int, vector<int> > productOfPrimes;
// Every number from both the array is iterated
// getProductOddOccuringPrimes function is called
// and the product of odd occurring primes is
// stored in the map productOfPrimes.
// A pair is printed if the product is same
for (int i = 0; i < n; ++i) {
// Generating the product of odd times
// occurring primes
int productPrimesOfA
= getProductOddOccuringPrimes(a[i]);
// Pushing the indices to the to the
// vector with the product of
// odd times occurring Primes
productOfPrimes[productPrimesOfA].push_back(i);
}
for (int i = 0; i < m; ++i) {
// Generating the product of odd times
// occurring Primes
int productPrimesOfB
= getProductOddOccuringPrimes(b[i]);
// Checking if productPrimesOfB
// lies in the productOfPrimes
if (productOfPrimes.find(productPrimesOfB)
!= productOfPrimes.end()) {
for (auto itr : productOfPrimes[productPrimesOfB]) {
countPairs++;
cout << " (" << b[i] << ", "
<< a[itr] << ") ";
}
}
}
if (countPairs <= 0)
cout << "No pairs Found!";
cout << endl;
}
// Driver function
int main()
{
sieve();
// N, M are size of array a and b respectively
int N = 5, M = 5;
int a[] = { 4, 1, 6, 35, 120 };
int b[] = { 24, 140, 4, 30, 1 };
// Function that prints the pairs
// whose product is a perfect square
printPairs(N, M, a, b);
return 0;
}
Java
// Java program to print pairs whose
// product is a perfect square
import java.util.*;
class GFG{
// Maximum number upto which sieve is performed
static final int MAXN = 100001;
// Array to perform Sieve of Eratosthenes
// and store prime numbers
static int []spf = new int[MAXN];
// Function to perform sieve of
// eratosthenes on the array spf.
static void sieve()
{
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
spf[i] = i;
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (spf[i] == i) {
for (int j = i * i; j < MAXN; j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to return the product of the
// odd occurring prime factors of a number
static int getProductOddOccuringPrimes(int x)
{
// Product of 1 with perfect square gives
// perfect square, 1 is returned for x = 1
if (x == 1)
return 1;
// Temporary container of prime factors
Vector<Integer> ret = new Vector<Integer>();
while (x != 1) {
ret.add(spf[x]);
x = x / spf[x];
}
// ans contains the product of primes
// which occurs odd number of times
int count = 1, ans = 1;
for (int i = 0, j = 1; j < ret.size(); ++j, ++i) {
if (ret.get(i) != ret.get(j)) {
if (count % 2 == 1)
ans *= ret.get(i);
count = 0;
}
count++;
}
// Checks if count is odd or not
if (count %2 == 1)
ans *= ret.get(ret.size() - 1);
return ans;
}
// Function to print the pairs whose product is
// a perfect square
static void printPairs(int n, int m, int a[], int b[])
{
int countPairs = 0;
// For storing the indices with same
// product of odd times occurring Primes as key
Map<Integer, Vector<Integer>> productOfPrimes =
new HashMap<Integer, Vector<Integer>>();
// Every number from both the array is iterated
// getProductOddOccuringPrimes function is called
// and the product of odd occurring primes is
// stored in the map productOfPrimes.
// A pair is printed if the product is same
for (int i = 0; i < n; ++i) {
// Generating the product of odd times
// occurring primes
int productPrimesOfA
= getProductOddOccuringPrimes(a[i]);
// Pushing the indices to the to the
// vector with the product of
// odd times occurring Primes
Vector<Integer> temp = new Vector<Integer>();
if(productOfPrimes.containsKey(productPrimesOfA))
for (Integer s:productOfPrimes.get(productPrimesOfA)){
temp.add(s);
}
temp.add(i);
productOfPrimes.put(productPrimesOfA, temp);
}
for (int i = 0; i < m; ++i)
{
// Generating the product of odd times
// occurring Primes
int productPrimesOfB
= getProductOddOccuringPrimes(b[i]);
// Checking if productPrimesOfB
// lies in the productOfPrimes
if (productOfPrimes.containsKey(productPrimesOfB)) {
for (Integer itr : productOfPrimes.get(productPrimesOfB)) {
countPairs++;
System.out.print(" (" + b[i]+ ", "
+ a[itr]+ ") ");
}
}
}
if (countPairs <= 0)
System.out.print("No pairs Found!");
System.out.println();
}
// Driver function
public static void main(String[] args)
{
sieve();
// N, M are size of array a and b respectively
int N = 5, M = 5;
int a[] = { 4, 1, 6, 35, 120 };
int b[] = { 24, 140, 4, 30, 1 };
// Function that prints the pairs
// whose product is a perfect square
printPairs(N, M, a, b);
}
}
// This code is contributed by 29AjayKumar
C#
// C# program to print pairs whose
// product is a perfect square
using System;
using System.Collections.Generic;
class GFG{
// Maximum number upto which sieve is performed
static readonly int MAXN = 100001;
// Array to perform Sieve of Eratosthenes
// and store prime numbers
static int []spf = new int[MAXN];
// Function to perform sieve of
// eratosthenes on the array spf.
static void sieve()
{
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
spf[i] = i;
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (spf[i] == i) {
for (int j = i * i; j < MAXN; j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to return the product of the
// odd occurring prime factors of a number
static int getProductOddOccuringPrimes(int x)
{
// Product of 1 with perfect square gives
// perfect square, 1 is returned for x = 1
if (x == 1)
return 1;
// Temporary container of prime factors
List<int> ret = new List<int>();
while (x != 1) {
ret.Add(spf[x]);
x = x / spf[x];
}
// ans contains the product of primes
// which occurs odd number of times
int count = 1, ans = 1;
for (int i = 0, j = 1; j < ret.Count; ++j, ++i) {
if (ret[i] != ret[j]) {
if (count % 2 == 1)
ans *= ret[i];
count = 0;
}
count++;
}
// Checks if count is odd or not
if (count %2 == 1)
ans *= ret[ret.Count - 1];
return ans;
}
// Function to print the pairs whose product is
// a perfect square
static void printPairs(int n, int m, int []a, int []b)
{
int countPairs = 0;
// For storing the indices with same
// product of odd times occurring Primes as key
Dictionary<int, List<int>> productOfPrimes =
new Dictionary<int, List<int>>();
// Every number from both the array is iterated
// getProductOddOccuringPrimes function is called
// and the product of odd occurring primes is
// stored in the map productOfPrimes.
// A pair is printed if the product is same
for (int i = 0; i < n; ++i) {
// Generating the product of odd times
// occurring primes
int productPrimesOfA
= getProductOddOccuringPrimes(a[i]);
// Pushing the indices to the to the
// vector with the product of
// odd times occurring Primes
List<int> temp = new List<int>();
if(productOfPrimes.ContainsKey(productPrimesOfA))
foreach (int s in productOfPrimes[productPrimesOfA]){
temp.Add(s);
}
temp.Add(i);
if(productOfPrimes.ContainsKey(productPrimesOfA))
productOfPrimes[productPrimesOfA] = temp;
else
productOfPrimes.Add(productPrimesOfA, temp);
}
for (int i = 0; i < m; ++i)
{
// Generating the product of odd times
// occurring Primes
int productPrimesOfB
= getProductOddOccuringPrimes(b[i]);
// Checking if productPrimesOfB
// lies in the productOfPrimes
if (productOfPrimes.ContainsKey(productPrimesOfB)) {
foreach (int itr in productOfPrimes[productPrimesOfB]) {
countPairs++;
Console.Write(" (" + b[i]+ ", "
+ a[itr]+ ") ");
}
}
}
if (countPairs <= 0)
Console.Write("No pairs Found!");
Console.WriteLine();
}
// Driver function
public static void Main(String[] args)
{
sieve();
// N, M are size of array a and b respectively
int N = 5, M = 5;
int []a = { 4, 1, 6, 35, 120 };
int []b = { 24, 140, 4, 30, 1 };
// Function that prints the pairs
// whose product is a perfect square
printPairs(N, M, a, b);
}
}
// This code is contributed by 29AjayKumar
Producción:
(24, 6) (140, 35) (4, 4) (4, 1) (30, 120) (1, 4) (1, 1)
Complejidad de tiempo: O(Klog(K)) donde K = max(N,M)
Publicación traducida automáticamente
Artículo escrito por ankiiitraj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA