Check if array can be sorted by swapping pairs having GCD equal to the smallest element in the array | Python3 implementation of the above approach ; Function to check if it is possible to sort array or not ; Store the smallest element ; Copy the original array ; Iterate over the given array ; Update smallest element ; Copy elements of arr to array B ; Sort original array ; Iterate over the given array ; If the i - th element is not in its sorted place ; Not possible to swap ; Driver Code ; Given array ; Function Call
import sys NEW_LINE def isPossible ( arr , N ) : NEW_LINE INDENT mn = sys . maxsize ; NEW_LINE B = [ 0 ] * N ; NEW_LINE for i in range ( N ) : NEW_LINE INDENT mn = min ( mn , arr [ i ] ) ; NEW_LINE B [ i ] = arr [ i ] ; NEW_LINE DEDENT arr . sort ( ) ; NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( arr [ i ] != B [ i ] ) : NEW_LINE INDENT if ( B [ i ] % mn != 0 ) : NEW_LINE INDENT print ( " No " ) ; NEW_LINE return ; NEW_LINE DEDENT DEDENT DEDENT print ( " Yes " ) ; NEW_LINE return ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 ; NEW_LINE arr = [ 4 , 3 , 6 , 6 , 2 , 9 ] ; NEW_LINE isPossible ( arr , N ) ; NEW_LINE DEDENT