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: 5
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)