Count of subarrays of an Array having all unique digits | Function to obtain the mask for any integer ; Function to count the number of ways ; Subarray must not be empty ; If subproblem has been solved ; Excluding this element in the subarray ; If there are no common digits then only this element can be included ; Calculate the new mask if this element is included ; Store and return the answer ; Function to find the count of subarray with all digits unique ; Initializing dp ; Driver Code
def getmask ( val ) : NEW_LINE INDENT mask = 0 NEW_LINE if val == 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT while ( val ) : NEW_LINE INDENT d = val % 10 ; NEW_LINE mask |= ( 1 << d ) NEW_LINE val = val // 10 NEW_LINE DEDENT return mask NEW_LINE DEDENT def countWays ( pos , mask , a , n ) : NEW_LINE INDENT if pos == n : NEW_LINE INDENT if mask > 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if dp [ pos ] [ mask ] != - 1 : NEW_LINE INDENT return dp [ pos ] [ mask ] NEW_LINE DEDENT count = 0 NEW_LINE count = ( count + countWays ( pos + 1 , mask , a , n ) ) NEW_LINE if ( getmask ( a [ pos ] ) & mask ) == 0 : NEW_LINE INDENT new_mask = ( mask | ( getmask ( a [ pos ] ) ) ) NEW_LINE count = ( count + countWays ( pos + 1 , new_mask , a , n ) ) NEW_LINE DEDENT dp [ pos ] [ mask ] = count NEW_LINE return count NEW_LINE DEDENT def numberOfSubarrays ( a , n ) : NEW_LINE INDENT return countWays ( 0 , 0 , a , n ) NEW_LINE DEDENT dp = [ [ - 1 for i in range ( cols ) ] for j in range ( rows ) ] NEW_LINE print ( numberOfSubarrays ( A , N ) ) NEW_LINE N = 4 NEW_LINE A = [ 1 , 12 , 23 , 34 ] NEW_LINE rows = 5000 NEW_LINE cols = 1100 NEW_LINE