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