Dada una array arr[] de N enteros positivos, la tarea es contar el número de elementos de la array que se pueden expresar como el producto de dos elementos distintos de la array o como un cuadrado de cualquier elemento de la array.
Ejemplos:
Entrada: N = 5, arr[] = {3, 2, 6, 18, 4}
Salida: 3
Explicación:
3 elementos de la array dada 6, 18 y 4 se pueden expresar como {2 * 3, 6 * 3, 2 * 2} respectivamente.Entrada: N = 6, arr[] = {5, 15, 3, 7, 10, 17}
Salida: 1
Explicación:
Solo 15 se puede expresar como 5 * 3.
Enfoque ingenuo:
el enfoque más simple es recorrer la array en el rango [0, N-1] y para cada número que tenga un valor de índice i dentro del rango dado, ejecutar un ciclo anidado sobre la misma array para encontrar los dos valores cuyo producto es arr[i]. Si se encuentra un par de números, imprima 1; de lo contrario, imprima 0 contra el índice correspondiente.
Complejidad temporal: O(N 3 )
Enfoque eficiente:
para resolver el problema, necesitamos encontrar todos los factores de cada elemento y, para cada elemento, verificar si algún par de factores de ese elemento está presente en la array o no. Siga los pasos a continuación para resolver el problema:
- Ordena la array dada en orden creciente.
- Ahora, recorra la array y para cada elemento, encuentre todos los pares de factores de ese elemento y verifique si alguno de los pares existe en la array o no usando la búsqueda binaria .
- Ordenar la array nos permite realizar una búsqueda binaria mientras buscamos factores, lo que reduce la complejidad computacional a O(logN) .
- Si se encuentra alguno de esos pares, aumente el conteo y pase al siguiente elemento y repita el mismo proceso.
- Imprime el conteo final de todos esos números en la array.
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;
// Stores all factors a number
vector<int> v[100000];
// Function to calculate and
// store in a vector
void div(int n)
{
for (int i = 2; i <= sqrt(n);
i++) {
if (n % i == 0) {
v[n].push_back(i);
}
}
}
// Function to return the count of
// array elements which are a
// product of two array elements
int prodof2elements(int arr[], int n)
{
int arr2[n];
// Copy elements into a
// a duplicate array
for (int i = 0; i < n; i++) {
arr2[i] = arr[i];
}
// Sort the duplicate array
sort(arr2, arr2 + n);
// Store the count of elements
int ans = 0;
for (int i = 0; i < n; i++) {
// If the factors are not
// calculated already
if (v[arr[i]].size() == 0)
div(arr[i]);
// Traverse its factors
for (auto j : v[arr[i]]) {
// If a pair of
// factors is found
if (binary_search(
arr2, arr2 + n, j)
and binary_search(
arr2, arr2 + n,
arr[i] / j)) {
ans++;
break;
}
}
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { 2, 1, 8, 4, 32, 18 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << prodof2elements(arr, N);
return 0;
}
Java
// Java Program to implement the
// above approach
import java.util.*;
class GFG{
// Stores all factors a number
static Vector<Integer>[] v =
new Vector[100000];
// Function to calculate and
// store in a vector
static void div(int n)
{
for (int i = 2;
i <= Math.sqrt(n); i++)
{
if (n % i == 0)
{
v[n].add(i);
}
}
}
// Function to return the count of
// array elements which are a
// product of two array elements
static int prodof2elements(int arr[],
int n)
{
int []arr2 = new int[n];
// Copy elements into a
// a duplicate array
for (int i = 0; i < n; i++)
{
arr2[i] = arr[i];
}
// Sort the duplicate
// array
Arrays.sort(arr2);
// Store the count
// of elements
int ans = 0;
for (int i = 0; i < n; i++)
{
// If the factors are not
// calculated already
if (v[arr[i]].size() == 0)
div(arr[i]);
// Traverse its factors
for (int j : v[arr[i]])
{
// If a pair of
// factors is found
if (Arrays.binarySearch(arr2, j) >= 0 &&
Arrays.binarySearch(arr2,
(int)arr[i] / j) >= 0)
{
ans++;
break;
}
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {2, 1, 8, 4, 32, 18};
int N = arr.length;
for (int i = 0; i < v.length; i++)
v[i] = new Vector<Integer>();
System.out.print(prodof2elements(arr, N));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to implement the # above approach import math # Stores all factors a number v = [[] for i in range(100000)] # Function to calculate and # store in a vector def div(n): global v for i in range(2, int(math.sqrt(n)) + 1): if (n % i == 0): v[n].append(i) # Function to return the count of # array elements which are a # product of two array elements def prodof2elements(arr, n): # Copy elements into a # a duplicate array arr2 = arr.copy() # Sort the duplicate array arr2.sort() # Store the count of elements ans = 0 for i in range(n): # If the factors are not # calculated already if (len(v[arr[i]]) == 0): div(arr[i]) # Traverse its factors for j in v[arr[i]]: # If a pair of # factors is found if j in arr2: if int(arr[i] / j) in arr2: ans += 1 break return ans # Driver Code arr = [ 2, 1, 8, 4, 32, 18 ] N = len(arr) print(prodof2elements(arr, N)) # This code is contributed by avanitrachhadiya2155
C#
// C# Program to implement the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Stores all factors a number
static List<int>[] v =
new List<int>[100000];
// Function to calculate and
// store in a vector
static void div(int n)
{
for (int i = 2;
i <= Math.Sqrt(n); i++)
{
if (n % i == 0)
{
v[n].Add(i);
}
}
}
// Function to return the count of
// array elements which are a
// product of two array elements
static int prodof2elements(int []arr,
int n)
{
int []arr2 = new int[n];
// Copy elements into a
// a duplicate array
for (int i = 0; i < n; i++)
{
arr2[i] = arr[i];
}
// Sort the duplicate
// array
Array.Sort(arr2);
// Store the count
// of elements
int ans = 0;
for (int i = 0; i < n; i++)
{
// If the factors are not
// calculated already
if (v[arr[i]].Count == 0)
div(arr[i]);
// Traverse its factors
foreach (int j in v[arr[i]])
{
// If a pair of
// factors is found
if (Array.BinarySearch(arr2, j) >= 0 &&
Array.BinarySearch(arr2,
(int)arr[i] / j) >= 0)
{
ans++;
break;
}
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {2, 1, 8, 4, 32, 18};
int N = arr.Length;
for (int i = 0; i < v.Length; i++)
v[i] = new List<int>();
Console.Write(prodof2elements(arr, N));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript implementation of above approach
// Stores all factors a number
let v = new Array(100000).fill(0).map(()=>[]);
// Function to calculate and
// store in a vector
function div(n)
{
for (let i = 2; i <= Math.sqrt(n);i++) {
if (n % i == 0) {
v[n].push(i);
}
}
}
// Function to return the count of
// array elements which are a
// product of two array elements
function prodof2elements(arr, n)
{
let arr2 = arr.slice(0,)
// Sort the duplicate array
arr2.sort((a,b)=>a-b);
// Store the count of elements
let ans = 0;
for (let i = 0; i < n; i++) {
// If the factors are not
// calculated already
if (v[arr[i]].length == 0)
div(arr[i]);
// Traverse its factors
for (let j of v[arr[i]]) {
// If a pair of
// factors is found
if (arr2.includes(j) && arr2.includes(Math.floor(arr[i]/j))){
ans++;
break;
}
}
}
return ans;
}
// Driver Code
let arr = [ 2, 1, 8, 4, 32, 18 ];
let N = arr.length;
document.write(prodof2elements(arr, N),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción:
3
Complejidad de tiempo: O(N 3/2 *log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nishitsharma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA