Total count of sorted numbers upto N digits in range [ L , R ] ( Magnificent necklace combinatorics problem ) | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int Count ( int N , int L , int R ) { vector < vector < int > > dp ( N , vector < int > ( R - L + 1 , 0 ) ) ; int ans = 0 ; for ( int i = 0 ; i < N ; i ++ ) { dp [ i ] [ 0 ] = 1 ; } for ( int i = 1 ; i < dp [ 0 ] . size ( ) ; i ++ ) { dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] + 1 ; } ans = dp [ 0 ] [ R - L ] ; for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 1 ; j < dp [ 0 ] . size ( ) ; j ++ ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + dp [ i ] [ j - 1 ] ; } ans += dp [ i ] [ R - L ] ; } return ans ; } int main ( ) { int N = 3 ; int L = 6 ; int R = 9 ; cout << Count ( N , L , R ) ; return 0 ; }