Minimizar la suma de K enteros positivos con LCM dado

Dados dos enteros positivos K y X , la tarea es encontrar la suma mínima posible de K enteros positivos ( repeticiones permitidas ) que tengan MCM X.

Ejemplos:

Entrada: K = 2, X = 6 
Salida:
Explicación: 
K(= 2) enteros positivos de suma mínima posible que tienen LCM X(= 6) son { 2, 3 }. 
Por lo tanto, la suma mínima posible de K(= 2) enteros positivos = (2 + 3) = 5. 
Por lo tanto, la salida requerida es 5.

Entrada: K = 3 X = 11 
Salida: 13 
Explicación: 
K(= 3) enteros positivos de suma mínima posible que tienen MCM X(= 11) son { 1, 1, 11 }. 
Por lo tanto, la suma mínima posible de K(= 3) enteros positivos = (1 + 1 + 11) = 13. 
Por lo tanto, la salida requerida es 13.

Enfoque: El problema se puede resolver usando la técnica Greedy . La idea es representar X en forma de producto de potencias primas . Seleccione K potencias principales de todas las potencias principales de X de todas las formas posibles y calcule sus respectivas sumas. Finalmente, imprima la mínima suma posible entre todos ellos. Siga los pasos a continuación para resolver el problema:

  • Inicialice una array , digamos primePow[] , para almacenar todas las potencias principales de X.
  • Si la longitud de la array primePow[] es menor o igual que K , incluya todos los elementos de la array de primePow[] en K enteros positivos y el elemento restante de K enteros positivos debe ser 1 . Finalmente, imprima la suma de K enteros positivos

Ilustración: 
Si K = 5, X = 240 
primePow[] = { 2 4 , 3 1 , 5 1 } = { 16, 3, 5 } 
K enteros positivos serán { 16, 3, 5, 1, 1 } 
Por lo tanto, la suma de k enteros positivos sera 26 
 

  • De lo contrario, divida la array primePow[] en K grupos de todas las formas posibles y calcule sus respectivas sumas. Finalmente, imprima la suma mínima de los K enteros positivos.

Si K = 3, X = 210 
primePow[] = { 2 1 , 3 1 , 5 1 , 5 1 } = { 2, 3, 5, 7 } 
Partición de la array primePow[] en { { 2, 3 }, { 5 }, { 7 } } 
210 = (2 * 3) * (5) * 7 = 6 * 5 * 7 
K enteros positivos serán { 6, 5, 7 } 
Por lo tanto, la suma de K(= 3) enteros positivos será tener 18 
 

A continuación se muestra la implementación de la implementación anterior:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the prime
// power of X
vector<int> primePower(int X)
{
 
    // Stores prime powers of X
    vector<int> primePow;
 
    // Iterate over the range [2, sqrt(X)]
    for (int i = 2; i * i <= X; i++) {
 
        // If X is divisible by i
        if (X % i == 0) {
 
            // Stores prime power
            int p = 1;
 
            // Calculate prime power
            // of X
            while (X % i == 0) {
 
                // Update X
                X /= i;
 
                // Update p
                p *= i;
            }
 
            // Insert prime powers
            // into primePow[]
            primePow.push_back(p);
        }
    }
 
    // If X exceeds 1
    if (X > 1) {
        primePow.push_back(X);
    }
 
    return primePow;
}
 
// Function to calculate the
// sum of array elements
int getSum(vector<int>& ar)
{
    // Stores sum of
    // array elements
    int sum = 0;
 
    // Traverse the array
    for (int i : ar) {
 
        // Update sum
        sum += i;
    }
 
    return sum;
}
 
// Function to partition array into K groups such
// that sum of elements of the K groups is minimum
int getMinSum(int pos, vector<int>& arr,
              vector<int>& primePow)
{
 
    // If count of prime powers
    // is equal to pos
    if (pos == primePow.size()) {
        return getSum(arr);
    }
 
    // Stores minimum sum of each
    // partition of arr[] into K groups
    int res = INT_MAX;
 
    // Traverse the array arr[]
    for (int i = 0; i < arr.size();
         i++) {
 
        // Include primePow[pos] into
        // i-th groups
        arr[i] *= primePow[pos];
 
        // Update res
        res = min(res, getMinSum(pos + 1,
                                 arr, primePow));
 
        // Remove factors[pos] from
        // i-th groups
        arr[i] /= primePow[pos];
    }
 
    return res;
}
 
// Utility function to calculate minimum sum
// of K positive integers whose LCM is X
int minimumSumWithGivenLCM(int k, int x)
{
    // Stores all prime powers of X
    vector<int> primePow = primePower(x);
 
    // Stores count of prime powers
    int n = primePow.size();
 
    // Stores minimum sum of K positive
    // integers whose LCM is X
    int sum = 0;
 
    // If n is less than
    // or equal to k
    if (n <= k) {
 
        // Traverse primePow[] array
        for (int i : primePow) {
 
            // Update sum
            sum += i;
        }
 
        // Update sum
        sum += k - n;
    }
 
    else {
 
        // arr[i]: Stores element in i-th group
        // by partitioning the primePow[] array
        vector<int> arr(k, 1);
 
        // Update sum
        sum = getMinSum(0, arr, primePow);
    }
 
    return sum;
}
 
// Driver Code
int main()
{
    int k = 3, x = 210;
 
    cout << minimumSumWithGivenLCM(k, x);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to find the prime
// power of X
static Vector<Integer> primePower(int X)
{
 
    // Stores prime powers of X
    Vector<Integer> primePow = new Vector<Integer>();
 
    // Iterate over the range [2, Math.sqrt(X)]
    for (int i = 2; i * i <= X; i++) {
 
        // If X is divisible by i
        if (X % i == 0) {
 
            // Stores prime power
            int p = 1;
 
            // Calculate prime power
            // of X
            while (X % i == 0) {
 
                // Update X
                X /= i;
 
                // Update p
                p *= i;
            }
 
            // Insert prime powers
            // into primePow[]
            primePow.add(p);
        }
    }
 
    // If X exceeds 1
    if (X > 1) {
        primePow.add(X);
    }
 
    return primePow;
}
 
// Function to calculate the
// sum of array elements
static int getSum(int []ar)
{
    // Stores sum of
    // array elements
    int sum = 0;
 
    // Traverse the array
    for (int i : ar) {
 
        // Update sum
        sum += i;
    }
 
    return sum;
}
 
// Function to partition array into K groups such
// that sum of elements of the K groups is minimum
static int getMinSum(int pos, int []arr,
              Vector<Integer> primePow)
{
 
    // If count of prime powers
    // is equal to pos
    if (pos == primePow.size()) {
        return getSum(arr);
    }
 
    // Stores minimum sum of each
    // partition of arr[] into K groups
    int res = Integer.MAX_VALUE;
 
    // Traverse the array arr[]
    for (int i = 0; i < arr.length;
         i++) {
 
        // Include primePow[pos] into
        // i-th groups
        arr[i] *= primePow.get(pos);
 
        // Update res
        res = Math.min(res, getMinSum(pos + 1,
                                 arr, primePow));
 
        // Remove factors[pos] from
        // i-th groups
        arr[i] /= primePow.get(pos);
    }
 
    return res;
}
 
// Utility function to calculate minimum sum
// of K positive integers whose LCM is X
static int minimumSumWithGivenLCM(int k, int x)
{
    // Stores all prime powers of X
    Vector<Integer> primePow = primePower(x);
 
    // Stores count of prime powers
    int n = primePow.size();
 
    // Stores minimum sum of K positive
    // integers whose LCM is X
    int sum = 0;
 
    // If n is less than
    // or equal to k
    if (n <= k) {
 
        // Traverse primePow[] array
        for (int i : primePow) {
 
            // Update sum
            sum += i;
        }
 
        // Update sum
        sum += k - n;
    }
 
    else {
 
        // arr[i]: Stores element in i-th group
        // by partitioning the primePow[] array
        int []arr = new int[k];
        Arrays.fill(arr, 1);
 
        // Update sum
        sum = getMinSum(0, arr, primePow);
    }
 
    return sum;
}
 
// Driver Code
public static void main(String[] args)
{
    int k = 3, x = 210;
 
    System.out.print(minimumSumWithGivenLCM(k, x));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to implement
# the above approach
 
# Function to find the prime
# power of X
def primePower(X):
 
    # Stores prime powers of X
    primePow = []
 
    # Iterate over the range [2, sqrt(X)]
    for i in range(2, X + 1):
 
        if i * i > X + 1:
            break
 
        # If X is divisible by i
        if (X % i == 0):
 
            # Stores prime power
            p = 1
 
            # Calculate prime power
            # of X
            while (X % i == 0):
 
                # Update X
                X //= i
 
                # Update p
                p *= i
 
            # Insert prime powers
            # into primePow[]
            primePow.append(p)
 
    # If X exceeds 1
    if (X > 1):
        primePow.append(X)
 
    return primePow
 
# Function to calculate the
# sum of array elements
def getSum(ar):
     
    # Stores sum of
    # array elements
    sum = 0
 
    # Traverse the array
    for i in ar:
 
        # Update sum
        sum += i
 
    return sum
 
# Function to partition array into K groups such
# that sum of elements of the K groups is minimum
def getMinSum(pos, arr, primePow):
 
    # If count of prime powers
    # is equal to pos
    if (pos == len(primePow)):
        return getSum(arr)
 
    # Stores minimum sum of each
    # partition of arr[] into K groups
    res = 10**9
 
    # Traverse the array arr[]
    for i in range(len(arr)):
         
        # Include primePow[pos] into
        # i-th groups
        arr[i] *= primePow[pos]
 
        # Update res
        res = min(res, getMinSum(pos + 1, arr, primePow))
 
        #Remove factors[pos] from
        #i-th groups
        arr[i] //= primePow[pos]
 
    return res
 
# Utility function to calculate minimum sum
# of K positive integers whose LCM is X
def minimumSumWithGivenLCM(k, x):
     
    # Stores all prime powers of X
    primePow = primePower(x)
 
    # Stores count of prime powers
    n = len(primePow)
 
    # Stores minimum sum of K positive
    # integers whose LCM is X
    sum = 0
 
    # If n is less than
    # or equal to k
    if (n <= k):
 
        # Traverse primePow[] array
        for i in primePow:
 
            # Update sum
            sum += i
 
        # Update sum
        sum += k - n
    else:
 
        # arr[i]: Stores element in i-th group
        # by partitioning the primePow[] array
        arr = [1] * (k)
 
        # Update sum
        sum = getMinSum(0, arr, primePow)
 
    return sum
 
# Driver Code
if __name__ == '__main__':
    k = 3
    x = 210
 
    print(minimumSumWithGivenLCM(k, x))
 
    # This code is contributed by mohit kumar 29

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the prime
// power of X
static List<int> primePower(int X)
{
     
    // Stores prime powers of X
    List<int> primePow = new List<int>();
 
    // Iterate over the range [2, Math.Sqrt(X)]
    for(int i = 2; i * i <= X; i++)
    {
         
        // If X is divisible by i
        if (X % i == 0)
        {
             
            // Stores prime power
            int p = 1;
 
            // Calculate prime power
            // of X
            while (X % i == 0)
            {
                 
                // Update X
                X /= i;
 
                // Update p
                p *= i;
            }
 
            // Insert prime powers
            // into primePow[]
            primePow.Add(p);
        }
    }
 
    // If X exceeds 1
    if (X > 1)
    {
        primePow.Add(X);
    }
    return primePow;
}
 
// Function to calculate the
// sum of array elements
static int getSum(int []ar)
{
     
    // Stores sum of
    // array elements
    int sum = 0;
 
    // Traverse the array
    foreach(int i in ar)
    {
         
        // Update sum
        sum += i;
    }
    return sum;
}
 
// Function to partition array into K groups such
// that sum of elements of the K groups is minimum
static int getMinSum(int pos, int []arr,
                List<int> primePow)
{
     
    // If count of prime powers
    // is equal to pos
    if (pos == primePow.Count)
    {
        return getSum(arr);
    }
 
    // Stores minimum sum of each
    // partition of []arr into K groups
    int res = int.MaxValue;
 
    // Traverse the array []arr
    for(int i = 0; i < arr.Length; i++)
    {
         
        // Include primePow[pos] into
        // i-th groups
        arr[i] *= primePow[pos];
 
        // Update res
        res = Math.Min(res, getMinSum(
            pos + 1, arr, primePow));
 
        // Remove factors[pos] from
        // i-th groups
        arr[i] /= primePow[pos];
    }
    return res;
}
 
// Utility function to calculate minimum sum
// of K positive integers whose LCM is X
static int minimumSumWithGivenLCM(int k, int x)
{
     
    // Stores all prime powers of X
    List<int> primePow = primePower(x);
 
    // Stores count of prime powers
    int n = primePow.Count;
 
    // Stores minimum sum of K positive
    // integers whose LCM is X
    int sum = 0;
 
    // If n is less than
    // or equal to k
    if (n <= k)
    {
         
        // Traverse primePow[] array
        foreach(int i in primePow)
        {
             
            // Update sum
            sum += i;
        }
 
        // Update sum
        sum += k - n;
    }
 
    else
    {
         
        // arr[i]: Stores element in i-th group
        // by partitioning the primePow[] array
        int []arr = new int[k];
        for(int l = 0; l < arr.Length; l++)
            arr[l] = 1;
 
        // Update sum
        sum = getMinSum(0, arr, primePow);
    }
    return sum;
}
 
// Driver Code
public static void Main(String[] args)
{
    int k = 3, x = 210;
 
    Console.Write(minimumSumWithGivenLCM(k, x));
}
}
 
// This code is contributed by aashish1995

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to find the prime
// power of X
function primePower(X)
{
    let primePow = [];
    // Iterate over the range [2, Math.sqrt(X)]
    for (let i = 2; i * i <= X; i++) {
  
        // If X is divisible by i
        if (X % i == 0) {
  
            // Stores prime power
            let p = 1;
  
            // Calculate prime power
            // of X
            while (X % i == 0) {
  
                // Update X
                X /= i;
  
                // Update p
                p *= i;
            }
  
            // Insert prime powers
            // into primePow[]
            primePow.push(p);
        }
    }
  
    // If X exceeds 1
    if (X > 1) {
        primePow.push(X);
    }
  
    return primePow;
}
 
// Function to calculate the
// sum of array elements
function getSum(ar)
{
    // Stores sum of
    // array elements
    let sum = 0;
  
    // Traverse the array
    for (let i=0;i< ar.length;i++) {
  
        // Update sum
        sum += ar[i];
    }
  
    return sum;
}
 
// Function to partition array into K groups such
// that sum of elements of the K groups is minimum
function getMinSum(pos,arr,primePow)
{
    // If count of prime powers
    // is equal to pos
    if (pos == primePow.length) {
        return getSum(arr);
    }
  
    // Stores minimum sum of each
    // partition of arr[] into K groups
    let res = Number.MAX_VALUE;
  
    // Traverse the array arr[]
    for (let i = 0; i < arr.length;
         i++) {
  
        // Include primePow[pos] into
        // i-th groups
        arr[i] *= primePow[pos];
  
        // Update res
        res = Math.min(res, getMinSum(pos + 1,
                                 arr, primePow));
  
        // Remove factors[pos] from
        // i-th groups
        arr[i] /= primePow[pos];
    }
  
    return res;
}
 
// Utility function to calculate minimum sum
// of K positive integers whose LCM is X
function minimumSumWithGivenLCM(k,x)
{
    // Stores all prime powers of X
    let primePow = primePower(x);
  
    // Stores count of prime powers
    let n = primePow.length;
  
    // Stores minimum sum of K positive
    // integers whose LCM is X
    let sum = 0;
  
    // If n is less than
    // or equal to k
    if (n <= k) {
  
        // Traverse primePow[] array
        for (let i=0;i< primePow.length;i++) {
  
            // Update sum
            sum += primePow[i];
        }
  
        // Update sum
        sum += k - n;
    }
  
    else {
  
        // arr[i]: Stores element in i-th group
        // by partitioning the primePow[] array
        let arr = new Array(k);
        for(let i=0;i<k;i++)
        {
            arr[i]=1;
        }
  
        // Update sum
        sum = getMinSum(0, arr, primePow);
    }
  
    return sum;
}
 
// Driver Code
let k = 3, x = 210;
  
document.write(minimumSumWithGivenLCM(k, x));
 
 
// This code is contributed by patel2127
 
</script>
Producción: 

18

 

Complejidad de tiempo: O(sqrt(X) + 3 Y ), donde Y es el conteo máximo de factores primos  
Espacio auxiliar: O(K + Y)

Publicación traducida automáticamente

Artículo escrito por akshume 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 *