Given two positive integers K and X, the task is to find the minimum possible sum of K positive integers ( repetitions allowed ) having LCM X.
Examples:
Input: K = 2, X = 6
Output: 5
Explanation:
K(= 2) positive integers of minimum possible sum having LCM X(= 6) are { 2, 3 }.
Therefore, the minimum possible sum of K(= 2) positive integers = (2 + 3) = 5.
Therefore, the required output is 5.Input: K = 3 X = 11
Output: 13
Explanation:
K(= 3) positive integers of minimum possible sum having LCM X(= 11) are { 1, 1, 11 }.
Therefore, the minimum possible sum of K(= 3) positive integers = (1 + 1 + 11) = 13.
Therefore, the required output is 13.
Approach: The problem can be solved using Greedy technique. The idea is to represent X in the form of a product of prime powers. Select K prime powers from all the prime powers of X in all possible ways and calculate their respective sums. Finally, print the minimum possible sum among all of them. Follow the steps below to solve the problem:
- Initialize an array, say primePow[], to store all the prime powers of X.
- If length of the array primePow[] is less than or equal to K, then include all the array elements of primePow[] in K positive integer and the remaining element Of K positive integers must be 1. Finally, print the sum of K positive integers
Illustration:
If K = 5, X = 240
primePow[] = { 24, 31, 51 } = { 16, 3, 5 }
K positive integers will be { 16, 3, 5, 1, 1 }
Therefore, the sum of K positive integers will be 26
- Otherwise, partition the primePow[] array into K groups in all possible ways and calculate their respective sums. Finally, print the minimum sum of the K positive integers.
If K = 3, X = 210
primePow[] = { 21, 31, 51, 51 } = { 2, 3, 5, 7 }
Partition primePow[] array into { { 2, 3 }, { 5 }, { 7 } }
210 = (2 * 3) * (5) * 7 = 6 * 5 * 7
K positive integers will be { 6, 5, 7 }
Therefore, the sum of K(= 3) positive integers will be 18
Below is the implementation of the above implementation:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the prime// power of Xvector<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 elementsint 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 minimumint 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 Xint 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 Codeint main(){ int k = 3, x = 210; cout << minimumSumWithGivenLCM(k, x); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to find the prime// power of Xstatic 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 elementsstatic 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 minimumstatic 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 Xstatic 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 Codepublic 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 Xdef 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 elementsdef 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 minimumdef 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 Xdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function to find the prime// power of Xstatic 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 elementsstatic 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 minimumstatic 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 Xstatic 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 Codepublic 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 Xfunction 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 elementsfunction 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 minimumfunction 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 Xfunction 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 Codelet k = 3, x = 210; document.write(minimumSumWithGivenLCM(k, x));// This code is contributed by patel2127</script> |
Output:
18
Time Complexity: O(sqrt(X) + 3Y), where Y is the maximum count of prime factors
Auxiliary Space: O(K + Y)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!