Igualar dos números multiplicando por sus factores primos un número mínimo de veces

Dados dos números X e Y , la tarea es hacer que ambos sean iguales multiplicando repetidamente con sus factores primos el número mínimo de veces.

Ejemplos:

Entrada: X = 36, Y = 48
Salida: 3
Explicación: 
Operación 1: Elija 2 (factor primo de X) y multiplique con X. Ahora, X = 72, Y = 48.
Operación 2: Elija 2 (factor primo de X ) y multiplique con X, Ahora, X = 144, Y = 48
Operación 3: Elija 3 (factor primo de Y) y multiplique con X. Ahora, X = 144, Y = 144

Entrada: X = 10, Y = 14
Salida: -1

Enfoque: La idea es que X e Y pueden hacerse iguales solo si todo factor primo de X está presente en Y y todo factor primo de Y está presente en X. Para contar las operaciones mínimas requeridas para igualarlos, siga los siguientes pasos:

  • Calcule el mcd de X e Y , digamos MCD y encuentre newX = X/GCD y newY = Y/GCD para eliminar los factores primos comunes .
  • Encuentre los factores primos con sus frecuencias de newX y newY .
  • Compruebe que cada factor primo de newX esté presente en Y( dividirá Y) y que cada factor primo de newY esté presente en X( dividirá X) . Si no , devuelve -1.  
  • Inicialice una variable, digamos ans =0, para almacenar la cantidad de operaciones requeridas.
  • Agregue todas las frecuencias de los números primos de newX y newY al ans .
  • Devuelve la respuesta .

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ program for the above approach 
#include <bits/stdc++.h>
using namespace std;
  
// Function to calculate total number of 
// prime factor with their prime factor 
unordered_map<int, int> PrimeFactor(int N)
{
    unordered_map<int, int> primef;
      
    // Iterate while the number is even 
    while (N % 2 == 0)
    {
        if (primef.count(2))
        {
            primef[2] += 1;
        }
        else 
        {
            primef[2] = 1;
        }
          
        // Reduce to half 
        N /= 2;
    }
      
    // Iterate up to sqrt(N) 
    for(int i = 3; i <= sqrt(N); i++) 
    {
          
        // Iterate while N has 
        // factors of i 
        while (N % i == 0) 
        {
            if (primef.count(i)) 
            {
                primef[i] += 1;
            }
            else 
            {
                primef[i] = 1;
            }
              
            // Removing one factor of i 
            N /= 2;
        }
    }
    if (N > 2)
    {
        primef[N] = 1;
    }
    return primef;
}
  
// Function to count the number of factors 
int CountToMakeEqual(int X, int Y)
{
      
    // Find the GCD 
    int gcdofXY = __gcd(X, Y);
      
    // Find multiples left in X and Y 
    int newX = Y / gcdofXY;
    int newY = X / gcdofXY;
      
    // Find prime factor of multiple 
    // left in X and Y 
    unordered_map<int, int> primeX;
    unordered_map<int, int> primeY;
    primeX = PrimeFactor(newX);
    primeY = PrimeFactor(newY);
      
    // Initialize ans 
    int ans = 0;
      
    // Check if it possible 
    // to obtain X or not 
    for(auto c : primeX) 
    {
        if (X % c.first != 0) 
        {
            return -1;
        }
        ans += primeX[c.first];
    }
      
    // Check if it possible to 
    // obtain Y or not 
    for(auto c : primeY) 
    {
        if (Y % c.first != 0)
        {
            return -1;
        }
        ans += primeY[c.first];
    }
      
    // return main ans 
    return ans;
}
  
// Driver code
int main()
{
      
    // Given Input 
    int X = 36;
    int Y = 48;
      
    // Function Call 
    int ans = CountToMakeEqual(X, Y);
    cout << ans << endl;
    return 0;
}
  
// This code is contributed by adarshsinghk

Java

// Java program for the above approach
import java.util.*;
public class Main
{
      
    static int gcd(int a, int b)
    {
           
        // Everything divides 0
        if (b == 0)
        {
            return a;
        }
        return gcd(b, a % b);
    }
       
    // Function to calculate total number of
    // prime factor with their prime factor
    static HashMap<Integer, Integer> PrimeFactor(int N)
    {
        HashMap<Integer, Integer> primef = new HashMap<Integer, Integer>();
           
        // Iterate while the number is even
        while (N % 2 == 0)
        {
            if (primef.containsKey(2))
            {
                primef.put(2, primef.get(2) + 1);
            }
            else
            {
                primef.put(2, 1);
            }
               
            // Reduce to half
            N = N / 2;
        }
           
        // Iterate up to sqrt(N)
        for(int i = 3; i <= Math.sqrt(N); i++)
        {
           
            // Iterate while N has
            // factors of i
            while (N % i == 0)
            {
                if (primef.containsKey(i))
                {
                    primef.put(i, primef.get(i) + 1);
                }
                else
                {
                    primef.put(i, 1);
                }
                   
                // Removing one factor of i
                N = N / 2;
            }
        }
        if (N > 2)
        {
            primef.put(N, 1);
        }
        return primef;
    }
       
    // Function to count the number of factors
    static int CountToMakeEqual(int X, int Y)
    {
       
        // Find the GCD
        int gcdofXY = gcd(X, Y);
           
        // Find multiples left in X and Y
        int newX = Y / gcdofXY;
        int newY = X / gcdofXY;
           
        // Find prime factor of multiple
        // left in X and Y
        HashMap<Integer, Integer> primeX = PrimeFactor(newX);
        HashMap<Integer, Integer> primeY = PrimeFactor(newY);
           
        // Initialize ans
        int ans = 0;
           
        // Check if it possible
        // to obtain X or not
        for (Map.Entry keys : primeX.entrySet()) {
            if (X % (int)keys.getKey() != 0)
            {
                return -1;
            }
            ans += primeX.get(keys.getKey());
        }
           
        // Check if it possible to
        // obtain Y or not
        for (Map.Entry keys : primeY.entrySet()) {
            if (Y % (int)keys.getKey() != 0)
            {
                return -1;
            }
            ans += primeY.get(keys.getKey());
        }
           
        // Return main ans
        return ans;
    }
  
    public static void main(String[] args) {
        // Given Input
        int X = 36;
        int Y = 48;
           
        // Function Call
        int ans = CountToMakeEqual(X, Y);
        System.out.println(ans);
    }
}
  
// This code is contributed by mukesh07.

Python3

# Python program for the above approach
import math
  
# Function to calculate total number of
# prime factor with their prime factor
  
  
def PrimeFactor(N):
    ANS = dict()
  
    # Iterate while the number is even
    while N % 2 == 0:
        if 2 in ANS:
            ANS[2] += 1
        else:
            ANS[2] = 1
  
        # Reduce to half
        N = N//2
  
    # Iterate up to sqrt(N)
    for i in range(3, int(math.sqrt(N))+1, 2):
  
        # Iterate while N has
        # factors of i
        while N % i == 0:
            if i in ANS:
                ANS[i] += 1
            else:
                ANS[i] = 1
  
            # Removing one factor of i
            N = N // i
  
    if 2 < N:
        ANS[N] = 1
  
    return ANS
  
  
# Function to count the number of factors
def CountToMakeEqual(X, Y):
  
    # Find the GCD
    GCD = math.gcd(X, Y)
  
    # Find multiples left in X and Y
    newY = X//GCD
    newX = Y//GCD
  
    # Find prime factor of multiple
    # left in X and Y
    primeX = PrimeFactor(newX)
    primeY = PrimeFactor(newY)
  
    # Initialize ans
    ans = 0
  
    # Check if it possible
    # to obtain X or not
    for factor in primeX:
  
        if X % factor != 0:
            return -1
        ans += primeX[factor]
  
    # Check if it possible to
    # obtain Y or not
    for factor in primeY:
  
        if Y % factor != 0:
            return -1
        ans += primeY[factor]
  
    # return main ans
    return ans
  
  
# Driver Code
if __name__ == "__main__":
  
    # Given Input
    X = 36
    Y = 48
  
    # Function Call
    ans = CountToMakeEqual(X, Y)
    print(ans)

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
  
class GFG{
      
static int gcd(int a, int b)
{
      
    // Everything divides 0
    if (b == 0)
    {
        return a;
    }
    return gcd(b, a % b);
}
  
// Function to calculate total number of
// prime factor with their prime factor
static Dictionary<int, int> PrimeFactor(int N)
{
    Dictionary<int, 
               int> primef = new Dictionary<int, 
                                            int>(); 
      
    // Iterate while the number is even
    while (N % 2 == 0)
    {
        if (primef.ContainsKey(2))
        {
            primef[2]++;
        }
        else
        {
            primef[2] = 1;
        }
          
        // Reduce to half
        N = N / 2;
    }
      
    // Iterate up to sqrt(N)
    for(int i = 3; i <= Math.Sqrt(N); i++)
    {
      
        // Iterate while N has
        // factors of i
        while (N % i == 0)
        {
            if (primef.ContainsKey(i))
            {
                primef[i]++;
            }
            else
            {
                primef[i] = 1;
            }
              
            // Removing one factor of i
            N = N / 2;
        }
    }
    if (N > 2)
    {
        primef[N] = 1;
    }
    return primef;
}
  
// Function to count the number of factors
static int CountToMakeEqual(int X, int Y)
{
  
    // Find the GCD
    int gcdofXY = gcd(X, Y);
      
    // Find multiples left in X and Y
    int newX = Y / gcdofXY;
    int newY = X / gcdofXY;
      
    // Find prime factor of multiple
    // left in X and Y
    Dictionary<int, int> primeX = PrimeFactor(newX);
    Dictionary<int, int> primeY = PrimeFactor(newY);
      
    // Initialize ans
    int ans = 0;
      
    // Check if it possible
    // to obtain X or not
    foreach(KeyValuePair<int, int> keys in primeX)
    {
        if (X % keys.Key != 0)
        {
            return -1;
        }
        ans += primeX[keys.Key];
    }
      
    // Check if it possible to
    // obtain Y or not
    foreach(KeyValuePair<int, int> keys in primeY)
    {
        if (Y % keys.Key != 0)
        {
            return -1;
        }
        ans += primeY[keys.Key];
    }
      
    // Return main ans
    return ans;
}
  
// Driver Code
static void Main() 
{
      
    // Given Input
    int X = 36;
    int Y = 48;
      
    // Function Call
    int ans = CountToMakeEqual(X, Y);
    Console.Write(ans);
}
}
  
// This code is contributed by rameshtravel07

Javascript

<script>
    // Javascript program for the above approach
      
    function gcd(a, b){
     
      // Everything divides 0
      if(b == 0){
        return a;
      }
  
      return gcd(b, a % b);
    }
  
    // Function to calculate total number of
    // prime factor with their prime factor
    function PrimeFactor(N)
    {
        let primef = new Map();
  
        // Iterate while the number is even
        while (N % 2 == 0)
        {
            if (primef.has(2))
            {
                primef.set(2, primef.get(2) + 1);
            }
            else
            {
                primef.set(2, 1);
            }
  
            // Reduce to half
            N = parseInt(N / 2, 10);
        }
  
        // Iterate up to sqrt(N)
        for(let i = 3; i <= Math.sqrt(N); i++)
        {
  
            // Iterate while N has
            // factors of i
            while (N % i == 0)
            {
                if (primef.has(i))
                {
                    primef.set(i, primef.get(i) + 1);
                }
                else
                {
                    primef.set(i, 1);
                }
  
                // Removing one factor of i
                N = parseInt(N / 2, 10);
            }
        }
        if (N > 2)
        {
            primef[N] = 1;
        }
        return primef;
    }
  
    // Function to count the number of factors
    function CountToMakeEqual(X, Y)
    {
  
        // Find the GCD
        let gcdofXY = gcd(X, Y);
  
        // Find multiples left in X and Y
        let newX = parseInt(Y / gcdofXY, 10);
        let newY = parseInt(X / gcdofXY, 10);
  
        // Find prime factor of multiple
        // left in X and Y
        let primeX = PrimeFactor(newX);
        let primeY = PrimeFactor(newY);
  
        // Initialize ans
        let ans = 0;
  
        // Check if it possible
        // to obtain X or not
        primeX.forEach((values,keys)=>
        {
            if (X % keys != 0)
            {
                return -1;
            }
            ans += primeX.get(keys);
        })
        ans+=1;
  
        // Check if it possible to
        // obtain Y or not
        primeY.forEach((values,keys)=>
        {
            if (Y % keys != 0)
            {
                return -1;
            }
            ans += primeY.get(keys);
        })
  
        // return main ans
        return ans;
    }
      
    // Given Input
    let X = 36;
    let Y = 48;
       
    // Function Call
    let ans = CountToMakeEqual(X, Y);
    document.write(ans);
  
// This code is contributed by decode2207.
</script>
Producción: 

3

 

Complejidad de tiempo: O(sqrt(max(X, Y)))
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por harshitkap00r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *