text: Rearrange array to maximize sum of GCD of array elements with their respective indices | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int findMaxValByRearrArr ( int arr [ ] , int N ) { sort ( arr , arr + N ) ; int res = 0 ; do { int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += __gcd ( i + 1 , arr [ i ] ) ; } res = max ( res , sum ) ; } while ( next_permutation ( arr , arr + N ) ) ; return res ; } int main ( ) { int arr [ ] = { 3 , 2 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << findMaxValByRearrArr ( arr , N ) ; return 0 ; }