Rearrange array to maximize sum of GCD of array elements with their respective indices | Java program to implement the above approach ; Function to find the maximum sum of GCD ( arr [ i ] , i ) by rearranging the array ; Sort the array in ascending order ; Stores maximum sum of GCD ( arr [ i ] , i ) by rearranging the array elements ; Generate all possible permutations of the array ; Stores sum of GCD ( arr [ i ] , i ) ; Traverse the array ; Update sum ; Update res ; Driver Code
import java . util . * ; class GFG { static int findMaxValByRearrArr ( int arr [ ] , int N ) { Arrays . sort ( arr ) ; int res = 0 ; do { int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += __gcd ( i + 1 , arr [ i ] ) ; } res = Math . max ( res , sum ) ; } while ( next_permutation ( arr ) ) ; return res ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } static boolean next_permutation ( int [ ] p ) { for ( int a = p . length - 2 ; a >= 0 ; -- a ) if ( p [ a ] < p [ a + 1 ] ) for ( int b = p . length - 1 ; ; -- b ) if ( p [ b ] > p [ a ] ) { int t = p [ a ] ; p [ a ] = p [ b ] ; p [ b ] = t ; for ( ++ a , b = p . length - 1 ; a < b ; ++ a , -- b ) { t = p [ a ] ; p [ a ] = p [ b ] ; p [ b ] = t ; } return true ; } return false ; } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 2 , 1 } ; int N = arr . length ; System . out . print ( findMaxValByRearrArr ( arr , N ) ) ; } }