Dada una lista de N números, encuentre dos números tales que el producto de los dos números tenga el número máximo de factores . Formalmente dados n números a0, a1, a2, …..an. Estamos obligados a encontrar dos números ai y aj tales que su multiplicación dé el número máximo de factores y devuelva el número de factores de ai * aj Restricciones 1 <= N <=100 1 <= ai <= 10^8 Ejemplos:
Input : [4, 3, 8]
Output : 8
3*4 = 12 which has 6 factors
3*8 = 24 which has 8 factors
4*8 = 32 which has 6 factors
for ai, aj = {3, 8} we have the
maximum number of factors 8
Un enfoque simple parece ser tomar dos números con factores primos máximos. Este enfoque podría no funcionar ya que los dos números seleccionados pueden tener muchos factores comunes y su producto podría no tener factores máximos. Por ejemplo, en [4, 3, 8], (4, 8) no es la respuesta, pero 3, 8 es la respuesta. Consideramos cada par de números. Para cada par, encontramos la unión de factores y finalmente devolvemos el par que tiene el máximo conteo en la unión.
C++
// C++ program to find the pair whose
// product has maximum factors.
#include <bits/stdc++.h>
using namespace std;
typedef unordered_map<int,int> u_map;
// Returns a map that has counts of individual
// factors in v[]
u_map countMap(vector<int> v)
{
u_map map;
for (size_t i = 0; i < v.size(); i++)
if (map.find(v[i]) != map.end())
map[v[i]]++;
else
map.insert({v[i], 1});
return map;
}
// Given two Numbers in the form of their
// prime factorized maps. Returns total
// number of factors of the product of
// those two numbers
int totalFactors(u_map m1, u_map m2)
{
// Find union of all factors.
for (auto it = m2.begin(); it != m2.end(); ++it) {
if (m1.find(it->first) != m1.end())
m1[it->first] += it->second;
else
m1.insert({ it->first, it->second });
}
int product = 1;
for (auto it = m1.begin(); it != m1.end(); it++)
product *= (it->second + 1);
return product;
}
// Prime factorization of a number is represented
// as an Unordered map
u_map primeFactorize(int n)
{
vector<int> pfac;
int temp = 2;
while (temp * temp <= n) {
if (n % temp == 0) {
pfac.push_back(temp);
n = n / temp;
}
else {
temp++;
}
}
if (n > 1)
pfac.push_back(n);
return countMap(pfac);
}
int maxProduct(int arr[], int n)
{
// vector containing of prime factorizations
// of every number in the array. Every element
// of vector contains factors and their counts.
vector<u_map> vum;
for (int i = 0; i < n; i++)
vum.push_back(primeFactorize(arr[i]));
// Consider every pair and find the pair with
// maximum factors.
int maxp = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
maxp = max(maxp,
totalFactors(vum[i], vum[j]));
}
}
return maxp;
}
// Driver code
int main()
{
int arr[] = { 4, 3, 8 };
cout << maxProduct(arr, 3);
return 0;
}
Java
import java.util.*;
public class GFG
{
// Java program to find the pair whose
// product has maximum factors.
// C++ TO JAVA CONVERTER WARNING: The following #include
// directive was ignored: #include <bits/stdc++.h>
// Returns a map that has counts of individual
// factors in v[]
public static HashMap<Integer, Integer>
countMap(ArrayList<Integer> v)
{
HashMap<Integer, Integer> map
= new HashMap<Integer, Integer>();
for (int i = 0; i < v.size(); i++) {
if (map.containsKey(v.get(i))) {
map.put(v.get(i), map.get(v.get(i)) + 1);
}
else {
map.put(v.get(i), 1);
}
}
return map;
}
// Given two Numbers in the form of their
// prime factorized maps. Returns total
// number of factors of the product of
// those two numbers
public static int
totalFactors(HashMap<Integer, Integer> m1,
HashMap<Integer, Integer> m2)
{
// Find union of all factors.
for (Map.Entry it : m2.entrySet()) {
int key = (int)it.getKey();
int value = (int)it.getValue();
if (m1.containsKey(key)) {
m1.put(key, m1.get(key) + value);
}
else {
m1.put(key, value);
}
}
int product = 1;
for (Map.Entry it : m1.entrySet()) {
product *= ((int)it.getValue() + 1);
}
return product;
}
// Prime factorization of a number is represented
// as an Unordered map
public static HashMap<Integer, Integer>
primeFactorize(int n)
{
ArrayList<Integer> pfac = new ArrayList<Integer>();
int temp = 2;
while (temp * temp <= n) {
if (n % temp == 0) {
pfac.add(temp);
n = n / temp;
}
else {
temp++;
}
}
if (n > 1) {
pfac.add(n);
}
return countMap(pfac);
}
public static int maxProduct(int[] arr, int n)
{
// vector containing of prime factorizations
// of every number in the array. Every element
// of vector contains factors and their counts.
ArrayList<HashMap<Integer, Integer> > vum
= new ArrayList<HashMap<Integer, Integer> >();
for (int i = 0; i < n; i++) {
vum.add(primeFactorize(arr[i]));
}
// Consider every pair and find the pair with
// maximum factors.
int maxp = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
maxp = Math.max(
maxp,
totalFactors(vum.get(i), vum.get(j)));
}
}
return maxp%10;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 4, 3, 8 };
System.out.print(maxProduct(arr, 3));
}
}
// The code is contributed by Aarti_Rathi
Python
# Python program to find the pair whose # product has maximum factors. from collections import Counter # Returns list of factors of n. def prime_factorize(n): primfac = [] d = 2 while d * d <= n: while (n % d) == 0: primfac.append(d) n //= d d += 1 if n > 1: primfac.append(n) return Counter(primfac) # Returns total factors in c1 and c2 def total_factors(c1, c2): c = c1 + c2 v = c.values() # calc product of each element + 1 p = 1 for i in v: p *=(i + 1) return p def max_product(arr): n = len(arr) # Loop through all the nc2 possibilities pfac = [] for i in arr: pfac.append(prime_factorize(i)) maxp = 0 for i, v1 in enumerate(arr): for j, v2 in enumerate(arr): if i == j: continue p = total_factors(pfac[i], pfac[j]) if(p>maxp): maxp = p return maxp if __name__ == '__main__': print max_product([4, 8, 3])
C#
// C# program to find the pair whose
// product has maximum factors.
using System;
using System.Collections.Generic;
public class GFG {
// Returns a map that has counts of individual
// factors in v[]
public static Dictionary<int, int> countMap(List<int> v)
{
Dictionary<int, int> map
= new Dictionary<int, int>();
for (int i = 0; i < v.Count; i++) {
if (map.ContainsKey(v[i])) {
map[v[i]]++;
}
else {
map[v[i]] = 1;
}
}
return map;
}
// Given two Numbers in the form of their
// prime factorized maps. Returns total
// number of factors of the product of
// those two numbers
public static int totalFactors(Dictionary<int, int> m1,
Dictionary<int, int> m2)
{
// Find union of all factors.
foreach(var it in m2)
{
int key = (int)it.Key;
int value = (int)it.Value;
if (m1.ContainsKey(key)) {
m1[key] += value;
}
else {
m1[key] = value;
}
}
int product = 1;
foreach(var it in m1)
{
product *= ((int)it.Value + 1);
}
return product;
}
// Prime factorization of a number is represented
// as an Unordered map
public static Dictionary<int, int> primeFactorize(int n)
{
List<int> pfac = new List<int>();
int temp = 2;
while (temp * temp <= n) {
if (n % temp == 0) {
pfac.Add(temp);
n = n / temp;
}
else {
temp++;
}
}
if (n > 1) {
pfac.Add(n);
}
return countMap(pfac);
}
public static int maxProduct(int[] arr, int n)
{
// vector containing of prime factorizations
// of every number in the array. Every element
// of vector contains factors and their counts.
List<Dictionary<int, int> > vum
= new List<Dictionary<int, int> >();
for (int i = 0; i < n; i++) {
vum.Add(primeFactorize(arr[i]));
}
// Consider every pair and find the pair with
// maximum factors.
int maxp = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
maxp = Math.Max(
maxp, totalFactors(vum[i], vum[j]));
}
}
return maxp % 10;
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 4, 3, 8 };
Console.Write(maxProduct(arr, 3));
}
}
// The code is contriubted by phasing17
Javascript
// JavaScript program to find the pair whose
// product has maximum factors.
// Returns a map that has counts of individual
// factors in v[]
function countMap(v)
{
let map = new Map();
for (let i = 0; i < v.length; i++)
if (map.has(v[i]))
map.set(v[i], map.get(v[i]) + 1);
else
map.set(v[i], 1);
return map;
}
// Given two Numbers in the form of their
// prime factorized maps. Returns total
// number of factors of the product of
// those two numbers
function totalFactors(M1, M2)
{
let m1 = new Map();
let m2 = new Map();
for(const [key, value] of M1){
m1.set(key, value);
}
for(const [key, value] of M2){
m2.set(key, value);
}
// Find union of all factors.
for(const [key, value] of m2){
if(m1.has(key.toString())){
m1.set(key, m1.get(key) + value);
}
else{
m1.set(key, value);
}
}
let product = 1;
for(const [key, value] of m1){
product = product * (value + 1);
}
return product;
}
// Prime factorization of a number is represented
// as an Unordered map
function primeFactorize(n)
{
let pfac = new Array();
let temp = 2;
while (temp * temp <= n) {
if (n % temp == 0) {
pfac.push(temp);
n = Math.floor(n / temp);
}
else {
temp = temp + 1;
}
}
if (n > 1)
pfac.push(n);
return countMap(pfac);
}
function maxProduct(arr, n)
{
// vector containing of prime factorizations
// of every number in the array. Every element
// of vector contains factors and their counts.
let vum = new Array();
for (let i = 0; i < n; i++){
vum.push(primeFactorize(arr[i]));
}
// Consider every pair and find the pair with
// maximum factors.
let maxp = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i == j){
continue;
}
maxp = Math.max(maxp, totalFactors(vum[i], vum[j]));
}
}
return maxp;
}
// Driver code
let arr = [4, 3, 8];
console.log(maxProduct(arr, 3));
// The code is contriubted by Gautam goel (gautamgoel962)
Producción:
8
Un enfoque alternativo es encontrar MCM de todos los pares y encontrar factores en todos los MCM. Finalmente devuelva el par cuyo MCM tiene factores máximos.
Publicación traducida automáticamente
Artículo escrito por sandeep tadepalli y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA