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
function countDivisibleSubseq ( str , n ) { let len = str . length ; let dp = new Array ( len ) ; for ( let i = 0 ; i < len ; i ++ ) { dp [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = 0 ; } } dp [ 0 ] [ ( str [ 0 ] - ' ' ) % n ] ++ ; for ( let i = 1 ; i < len ; i ++ ) { dp [ i ] [ ( str [ i ] - ' ' ) % n ] ++ ; for ( let j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] += dp [ i - 1 ] [ j ] ; dp [ i ] [ ( j * 10 + ( str [ i ] - ' ' ) ) % n ] += dp [ i - 1 ] [ j ] ; } } return dp [ len - 1 ] [ 0 ] ; } let str = " " ; let n = 4 ; document . write ( countDivisibleSubseq ( str , n ) ) ;