Count of sub | JavaScript implementation of the approach ; Function to return the total number of required sub - sets ; Variable to store total elements which on dividing by 3 give remainder 0 , 1 and 2 respectively ; Create a dp table ; Process for n states and store the sum ( mod 3 ) for 0 , 1 and 2 ; Use of MOD for large numbers ; Final answer store at dp [ n - 1 ] [ 0 ] ; Driver Program
let MOD = 1000000007 ; function totalSubSets ( n , l , r ) { let zero = Math . floor ( r / 3 ) - Math . ceil ( l / 3 ) + 1 ; let one = Math . floor ( ( r - 1 ) / 3 ) - Math . ceil ( ( l - 1 ) / 3 ) + 1 ; let two = Math . floor ( ( r - 2 ) / 3 ) - Math . ceil ( ( l - 2 ) / 3 ) + 1 ; let dp = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = new Array ( 3 ) ; for ( let j = 0 ; j < 3 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } dp [ 0 ] [ 0 ] = zero ; dp [ 0 ] [ 1 ] = one ; dp [ 0 ] [ 2 ] = two ; for ( let i = 1 ; i < n ; ++ i ) { dp [ i ] [ 0 ] = ( ( dp [ i - 1 ] [ 0 ] * zero ) + ( dp [ i - 1 ] [ 1 ] * two ) + ( dp [ i - 1 ] [ 2 ] * one ) ) % MOD ; dp [ i ] [ 1 ] = ( ( dp [ i - 1 ] [ 0 ] * one ) + ( dp [ i - 1 ] [ 1 ] * zero ) + ( dp [ i - 1 ] [ 2 ] * two ) ) % MOD ; dp [ i ] [ 2 ] = ( ( dp [ i - 1 ] [ 0 ] * two ) + ( dp [ i - 1 ] [ 1 ] * one ) + ( dp [ i - 1 ] [ 2 ] * zero ) ) % MOD ; } return dp [ n - 1 ] [ 0 ] ; } let n = 5 ; let l = 10 ; let r = 100 ; document . write ( totalSubSets ( n , l , r ) ) ;