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 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> |
18
Time Complexity: O(sqrt(X) + 3Y), where Y is the maximum count of prime factors
Auxiliary Space: O(K + Y)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!