Number of subsequences in a string divisible by n | Returns count of subsequences of str divisible by n . ; division by n can leave only n remainder [ 0. . n - 1 ] . dp [ i ] [ j ] indicates number of subsequences in string [ 0. . i ] which leaves remainder j after division by n . ; Filling value for first digit in str ; start a new subsequence with index i ; exclude i 'th character from all the  current subsequences of string [0...i-1] ; include i 'th character in all the current  subsequences of string [0...i-1] ; Driver code
def countDivisibleSubseq ( str , n ) : NEW_LINE INDENT l = len ( str ) NEW_LINE dp = [ [ 0 for x in range ( l ) ] for y in range ( n ) ] NEW_LINE dp [ 0 ] [ ( ord ( str [ 0 ] ) - ord ( '0' ) ) % n ] += 1 NEW_LINE for i in range ( 1 , l ) : NEW_LINE INDENT dp [ i ] [ ( ord ( str [ i ] ) - ord ( '0' ) ) % n ] += 1 NEW_LINE for j in range ( n ) : NEW_LINE INDENT dp [ i ] [ j ] += dp [ i - 1 ] [ j ] NEW_LINE dp [ i ] [ ( j * 10 + ( ord ( str [ i ] ) - ord ( '0' ) ) ) % n ] += dp [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT return dp [ l - 1 ] [ 0 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str = "1234" NEW_LINE n = 4 NEW_LINE print ( countDivisibleSubseq ( str , n ) ) NEW_LINE DEDENT