Total count of sorted numbers upto N digits in range [ L , R ] ( Magnificent necklace combinatorics problem ) | Function to count total number of ways ; Stores all DP - states ; Stores the result ; Traverse the range [ 0 , N ] ; Traverse the range [ 1 , R - L ] ; Update dp [ i ] [ j ] ; Assign dp [ 0 ] [ R - L ] to ans ; Traverse the range [ 1 , N ] ; Traverse the range [ 1 , R - L ] ; Update dp [ i ] [ j ] ; Increment ans by dp [ i - 1 ] [ j ] ; Return ans ; Driver Code ; Input ; Function call
def Count ( N , L , R ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( R - L + 1 ) ] for i in range ( N ) ] NEW_LINE ans = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 1 NEW_LINE DEDENT for i in range ( 1 , len ( dp [ 0 ] ) ) : NEW_LINE INDENT dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] + 1 NEW_LINE DEDENT ans = dp [ 0 ] [ R - L ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( 1 , len ( dp [ 0 ] ) ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + dp [ i ] [ j - 1 ] NEW_LINE DEDENT ans += dp [ i ] [ R - L ] NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE L = 6 NEW_LINE R = 9 NEW_LINE print ( Count ( N , L , R ) ) NEW_LINE DEDENT