Dadas dos arrays arr1[] y arr2[] de tamaños N y M donde 0 ≤ arr1[i], arr2[i] ≤ 1000 para todas las i válidas , la tarea es tomar un elemento de la primera array y un elemento de la segunda array tal que ambos son números feos. Lo llamamos un par (a, b). Tienes que encontrar el conteo de todos esos pares distintos. Tenga en cuenta que (a, b) y (b, a) no son distintos.
Los números feos son números cuyos únicos factores primos son 2, 3 o 5 .
La secuencia 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ….. muestra los primeros números feos. Por convención, 1 está incluido.
Ejemplos:
Entrada: arr1[] = {7, 2, 3, 14}, arr2[] = {2, 11, 10}
Salida: 4
Todos los pares distintos son (2, 2), (2, 10), (3, 2) ) y (3, 10)
Entrada: arr1[] = {1, 2, 3}, arr2[] = {1, 1}
Salida: 3
Todos los pares distintos son (1, 1), (1, 2) y ( 1, 3)
Acercarse:
- Primero genere todos los números feos e insértelos en un conjunto desordenado s1.
- Tome otro conjunto vacío s2.
- Ejecute dos bucles anidados para generar todos los pares posibles de las dos arrays tomando un elemento de la primera array (llámelo a) y uno de la segunda array (llámelo b).
- Compruebe si a está presente en s1. En caso afirmativo, compruebe cada elemento de arr2[] si también está presente en s1.
- Si tanto a como b son números feos, inserte el par (a, b) en s2 si a es menor que b, o (b, a) en caso contrario. Esto se hace para evitar la duplicación.
- El total de pares es el tamaño del conjunto s2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the nth ugly number
unsigned uglyNumber(int n)
{
// To store ugly numbers
int ugly[n];
int i2 = 0, i3 = 0, i5 = 0;
int next_multiple_of_2 = 2;
int next_multiple_of_3 = 3;
int next_multiple_of_5 = 5;
int next_ugly_no = 1;
ugly[0] = 1;
for (int i = 1; i < n; i++) {
next_ugly_no = min(next_multiple_of_2,
min(next_multiple_of_3,
next_multiple_of_5));
ugly[i] = next_ugly_no;
if (next_ugly_no == next_multiple_of_2) {
i2 = i2 + 1;
next_multiple_of_2 = ugly[i2] * 2;
}
if (next_ugly_no == next_multiple_of_3) {
i3 = i3 + 1;
next_multiple_of_3 = ugly[i3] * 3;
}
if (next_ugly_no == next_multiple_of_5) {
i5 = i5 + 1;
next_multiple_of_5 = ugly[i5] * 5;
}
}
return next_ugly_no;
}
// Function to return the required count of pairs
int totalPairs(int arr1[], int arr2[], int n, int m)
{
unordered_set<int> s1;
int i = 1;
// Insert ugly numbers in set
// which are less than 1000
while (1) {
int next_ugly_number = uglyNumber(i);
if (next_ugly_number > 1000)
break;
s1.insert(next_ugly_number);
i++;
}
// Set is used to avoid duplicate pairs
set<pair<int, int> > s2;
for (int i = 0; i < n; i++) {
// Check if arr1[i] is an ugly number
if (s1.find(arr1[i]) != s1.end()) {
for (int j = 0; j < m; j++) {
// Check if arr2[i] is an ugly number
if (s1.find(arr2[j]) != s1.end()) {
if (arr1[i] < arr2[j])
s2.insert(make_pair(arr1[i], arr2[j]));
else
s2.insert(make_pair(arr2[j], arr1[i]));
}
}
}
}
// Return the size of the set s2
return s2.size();
}
// Driver code
int main()
{
int arr1[] = { 3, 7, 1 };
int arr2[] = { 5, 1, 10, 4 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int m = sizeof(arr2) / sizeof(arr2[0]);
cout << totalPairs(arr1, arr2, n, m);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to get the nth ugly number
static int uglyNumber(int n)
{
// To store ugly numbers
int []ugly = new int[n];
int i2 = 0, i3 = 0, i5 = 0;
int next_multiple_of_2 = 2;
int next_multiple_of_3 = 3;
int next_multiple_of_5 = 5;
int next_ugly_no = 1;
ugly[0] = 1;
for (int i = 1; i < n; i++)
{
next_ugly_no = Math.min(next_multiple_of_2,
Math.min(next_multiple_of_3,
next_multiple_of_5));
ugly[i] = next_ugly_no;
if (next_ugly_no == next_multiple_of_2)
{
i2 = i2 + 1;
next_multiple_of_2 = ugly[i2] * 2;
}
if (next_ugly_no == next_multiple_of_3)
{
i3 = i3 + 1;
next_multiple_of_3 = ugly[i3] * 3;
}
if (next_ugly_no == next_multiple_of_5)
{
i5 = i5 + 1;
next_multiple_of_5 = ugly[i5] * 5;
}
}
return next_ugly_no;
}
// Function to return the required count of pairs
static int totalPairs(int arr1[], int arr2[],
int n, int m)
{
HashSet<Integer> s1 = new HashSet<Integer>();
int i = 1;
// Insert ugly numbers in set
// which are less than 1000
while (true)
{
int next_ugly_number = uglyNumber(i);
if (next_ugly_number > 1000)
break;
s1.add(next_ugly_number);
i++;
}
// Set is used to avoid duplicate pairs
HashSet<pair> s2 = new HashSet<pair>();
for (i = 0; i < n; i++)
{
// Check if arr1[i] is an ugly number
if (s1.contains(arr1[i]))
{
for (int j = 0; j < m; j++)
{
// Check if arr2[i] is an ugly number
if (s1.contains(arr2[j]))
{
if (arr1[i] < arr2[j])
s2.add(new pair(arr1[i], arr2[j]));
else
s2.add(new pair(arr2[j], arr1[i]));
}
}
}
}
// Return the size of the set s2
return s2.size();
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 3, 7, 1 };
int arr2[] = { 5, 1, 10, 4 };
int n = arr1.length;
int m = arr2.length;
System.out.println(totalPairs(arr1, arr2, n, m));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach # Function to get the nth ugly number def uglyNumber(n): # To store ugly numbers ugly = [None] * n i2 = i3 = i5 = 0 next_multiple_of_2 = 2 next_multiple_of_3 = 3 next_multiple_of_5 = 5 next_ugly_no = 1 ugly[0] = 1 for i in range(1, n): next_ugly_no = min(next_multiple_of_2, min(next_multiple_of_3, next_multiple_of_5)) ugly[i] = next_ugly_no if (next_ugly_no == next_multiple_of_2): i2 = i2 + 1 next_multiple_of_2 = ugly[i2] * 2 if (next_ugly_no == next_multiple_of_3): i3 = i3 + 1 next_multiple_of_3 = ugly[i3] * 3 if (next_ugly_no == next_multiple_of_5): i5 = i5 + 1 next_multiple_of_5 = ugly[i5] * 5 return next_ugly_no # Function to return the required count of pairs def totalPairs(arr1, arr2, n, m): s1 = set() i = 1 # Insert ugly numbers in set # which are less than 1000 while True: next_ugly_number = uglyNumber(i) if (next_ugly_number > 1000): break s1.add(next_ugly_number) i += 1 # Set is used to avoid duplicate pairs s2 = set() for i in range(0, n): # Check if arr1[i] is an ugly number if arr1[i] in s1: for j in range(0, m): # Check if arr2[i] is an ugly number if arr2[j] in s1: if (arr1[i] < arr2[j]): s2.add((arr1[i], arr2[j])) else: s2.add((arr2[j], arr1[i])) # Return the size of the set s2 return len(s2) # Driver code if __name__ == "__main__": arr1 = [3, 7, 1] arr2 = [5, 1, 10, 4] n = len(arr1) m = len(arr2) print(totalPairs(arr1, arr2, n, m)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
public class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to get the nth ugly number
static int uglyNumber(int n)
{
// To store ugly numbers
int []ugly = new int[n];
int i2 = 0, i3 = 0, i5 = 0;
int next_multiple_of_2 = 2;
int next_multiple_of_3 = 3;
int next_multiple_of_5 = 5;
int next_ugly_no = 1;
ugly[0] = 1;
for (int i = 1; i < n; i++)
{
next_ugly_no = Math.Min(next_multiple_of_2,
Math.Min(next_multiple_of_3,
next_multiple_of_5));
ugly[i] = next_ugly_no;
if (next_ugly_no == next_multiple_of_2)
{
i2 = i2 + 1;
next_multiple_of_2 = ugly[i2] * 2;
}
if (next_ugly_no == next_multiple_of_3)
{
i3 = i3 + 1;
next_multiple_of_3 = ugly[i3] * 3;
}
if (next_ugly_no == next_multiple_of_5)
{
i5 = i5 + 1;
next_multiple_of_5 = ugly[i5] * 5;
}
}
return next_ugly_no;
}
// Function to return the required count of pairs
static int totalPairs(int []arr1, int []arr2,
int n, int m)
{
HashSet<int> s1 = new HashSet<int>();
int i = 1;
// Insert ugly numbers in set
// which are less than 1000
while (true)
{
int next_ugly_number = uglyNumber(i);
if (next_ugly_number > 1000)
break;
s1.Add(next_ugly_number);
i++;
}
// Set is used to avoid duplicate pairs
HashSet<pair> s2 = new HashSet<pair>();
for (i = 0; i < n; i++)
{
// Check if arr1[i] is an ugly number
if (s1.Contains(arr1[i]))
{
for (int j = 0; j < m; j++)
{
// Check if arr2[i] is an ugly number
if (s1.Contains(arr2[j]))
{
if (arr1[i] < arr2[j])
s2.Add(new pair(arr1[i],
arr2[j]));
else
s2.Add(new pair(arr2[j],
arr1[i]));
}
}
}
}
// Return the size of the set s2
return s2.Count;
}
// Driver code
public static void Main(String[] args)
{
int []arr1 = { 3, 7, 1 };
int []arr2 = { 5, 1, 10, 4 };
int n = arr1.Length;
int m = arr2.Length;
Console.WriteLine(totalPairs(arr1, arr2, n, m));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Function to get the nth ugly number
function uglyNumber(n) {
// To store ugly numbers
let ugly = new Array(n);
let i2 = 0, i3 = 0, i5 = 0;
let next_multiple_of_2 = 2;
let next_multiple_of_3 = 3;
let next_multiple_of_5 = 5;
let next_ugly_no = 1;
ugly[0] = 1;
for (let i = 1; i < n; i++) {
next_ugly_no = Math.min(next_multiple_of_2,
Math.min(next_multiple_of_3,
next_multiple_of_5));
ugly[i] = next_ugly_no;
if (next_ugly_no == next_multiple_of_2) {
i2 = i2 + 1;
next_multiple_of_2 = ugly[i2] * 2;
}
if (next_ugly_no == next_multiple_of_3) {
i3 = i3 + 1;
next_multiple_of_3 = ugly[i3] * 3;
}
if (next_ugly_no == next_multiple_of_5) {
i5 = i5 + 1;
next_multiple_of_5 = ugly[i5] * 5;
}
}
return next_ugly_no;
}
// Function to return the required count of pairs
function totalPairs(arr1, arr2, n, m) {
let s1 = new Set();
let i = 1;
// Insert ugly numbers in set
// which are less than 1000
while (1) {
let next_ugly_number = uglyNumber(i);
if (next_ugly_number > 1000)
break;
s1.add(next_ugly_number);
i++;
}
// Set is used to avoid duplicate pairs
let s2 = new Set();
for (let i = 0; i < n; i++) {
// Check if arr1[i] is an ugly number
if (s1.has(arr1[i])) {
for (let j = 0; j < m; j++) {
// Check if arr2[i] is an ugly number
if (s1.has(arr2[j])) {
if (arr1[i] < arr2[j])
s2.add([arr1[i], arr2[j]]);
else
s2.add([arr2[j], arr1[i]]);
}
}
}
}
// Return the size of the set s2
return s2.size;
}
// Driver code
let arr1 = [3, 7, 1];
let arr2 = [5, 1, 10, 4];
let n = arr1.length;
let m = arr2.length;
document.write(totalPairs(arr1, arr2, n, m));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
8
Complejidad de tiempo : O(k 2 +n*m*log(n+m)) donde k = 1000 y n & m son los tamaños de la array
Espacio auxiliar : O(k+n+m)
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA