Smallest number dividing minimum number of elements in the Array | Function to return the smallest number that divides minimum number of elements ; m stores the maximum in the array ; Frequency table ; Loop to factorize ; sqrt factorization of the numbers ; Finding the smallest number with zero multiples ; Driver code
def findMin ( arr , n ) : NEW_LINE INDENT m = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT m = max ( m , arr [ i ] ) NEW_LINE DEDENT cnt = [ 0 ] * ( m + 2 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT j = 1 NEW_LINE while j * j <= arr [ i ] : NEW_LINE INDENT if ( arr [ i ] % j == 0 ) : NEW_LINE INDENT if ( j * j == arr [ i ] ) : NEW_LINE INDENT cnt [ j ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt [ j ] += 1 NEW_LINE cnt [ arr [ i ] // j ] += 1 NEW_LINE DEDENT DEDENT j += 1 NEW_LINE DEDENT DEDENT for i in range ( 1 , m + 2 ) : NEW_LINE INDENT if ( cnt [ i ] == 0 ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT arr = [ 2 , 12 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findMin ( arr , n ) ) NEW_LINE