Partition array into minimum number of equal length subsets consisting of a single distinct value | Python3 program to implement the above approach ; Function to find the minimum count of subsets by partitioning the array with given conditions ; Store frequency of each distinct element of the array ; Traverse the array ; Update frequency of arr [ i ] ; Stores GCD of frequency of each distinct element of the array ; Update freqGCD ; Driver Code
from math import gcd NEW_LINE def CntOfSubsetsByPartitioning ( arr , N ) : NEW_LINE INDENT freq = { } NEW_LINE for i in range ( N ) : NEW_LINE INDENT freq [ arr [ i ] ] = freq . get ( arr [ i ] , 0 ) + 1 NEW_LINE DEDENT freqGCD = 0 NEW_LINE for i in freq : NEW_LINE INDENT freqGCD = gcd ( freqGCD , freq [ i ] ) NEW_LINE DEDENT return ( N ) // freqGCD NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 4 , 3 , 2 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE print ( CntOfSubsetsByPartitioning ( arr , N ) ) NEW_LINE DEDENT