Rearrange array to maximize sum of GCD of array elements with their respective indices | 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
def findMaxValByRearrArr ( arr , N ) : NEW_LINE INDENT arr . sort ( ) NEW_LINE res = 0 NEW_LINE while ( True ) : NEW_LINE INDENT Sum = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT Sum += __gcd ( i + 1 , arr [ i ] ) NEW_LINE DEDENT res = max ( res , Sum ) NEW_LINE if ( not next_permutation ( arr ) ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT def __gcd ( a , b ) : NEW_LINE INDENT if b == 0 : NEW_LINE INDENT return a NEW_LINE DEDENT else : NEW_LINE INDENT return __gcd ( b , a % b ) NEW_LINE DEDENT DEDENT def next_permutation ( p ) : NEW_LINE INDENT for a in range ( len ( p ) - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( p [ a ] < p [ a + 1 ] ) : NEW_LINE INDENT b = len ( p ) - 1 NEW_LINE while True : NEW_LINE INDENT if ( p [ b ] > p [ a ] ) : NEW_LINE INDENT t = p [ a ] NEW_LINE p [ a ] = p [ b ] NEW_LINE p [ b ] = t NEW_LINE a += 1 NEW_LINE b = len ( p ) - 1 NEW_LINE while a < b : NEW_LINE INDENT t = p [ a ] NEW_LINE p [ a ] = p [ b ] NEW_LINE p [ b ] = t NEW_LINE a += 1 NEW_LINE b -= 1 NEW_LINE DEDENT return True NEW_LINE DEDENT b -= 1 NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT arr = [ 3 , 2 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE print ( findMaxValByRearrArr ( arr , N ) ) NEW_LINE