Count of sub | Python3 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 Code
import math NEW_LINE def totalSubSets ( n , l , r ) : NEW_LINE INDENT MOD = 1000000007 ; NEW_LINE zero = ( math . floor ( r / 3 ) - math . ceil ( l / 3 ) + 1 ) ; NEW_LINE one = ( math . floor ( ( r - 1 ) / 3 ) - math . ceil ( ( l - 1 ) / 3 ) + 1 ) ; NEW_LINE two = ( math . floor ( ( r - 2 ) / 3 ) - math . ceil ( ( l - 2 ) / 3 ) + 1 ) ; NEW_LINE dp = [ [ 0 for x in range ( 3 ) ] for y in range ( n ) ] NEW_LINE dp [ 0 ] [ 0 ] = zero ; NEW_LINE dp [ 0 ] [ 1 ] = one ; NEW_LINE dp [ 0 ] [ 2 ] = two ; NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT dp [ i ] [ 0 ] = ( ( dp [ i - 1 ] [ 0 ] * zero ) + ( dp [ i - 1 ] [ 1 ] * two ) + ( dp [ i - 1 ] [ 2 ] * one ) ) % MOD ; NEW_LINE dp [ i ] [ 1 ] = ( ( dp [ i - 1 ] [ 0 ] * one ) + ( dp [ i - 1 ] [ 1 ] * zero ) + ( dp [ i - 1 ] [ 2 ] * two ) ) % MOD ; NEW_LINE dp [ i ] [ 2 ] = ( ( dp [ i - 1 ] [ 0 ] * two ) + ( dp [ i - 1 ] [ 1 ] * one ) + ( dp [ i - 1 ] [ 2 ] * zero ) ) % MOD ; NEW_LINE DEDENT return dp [ n - 1 ] [ 0 ] ; NEW_LINE DEDENT n = 5 ; NEW_LINE l = 10 ; NEW_LINE r = 100 ; NEW_LINE print ( totalSubSets ( n , l , r ) ) ; NEW_LINE