Count numbers in a range with digit sum divisible by K having first and last digit different | C ++ Program to count numbers in a range with digit sum divisible by K having first and last digit different ; For calculating the upper bound of the sequence . ; checking whether the sum of digits = 0 or not and the corner case as number equal to 1 ; If the state is visited then return the answer of this state directly . ; for checking whether digit to be placed is up to upper bound at the position pos or upto 9 ; calculating new digit sum modulo k ; check if there is a prefix of 0 s and current digit != 0 ; Then current digit will be the starting digit ; Update the boolean flag that the starting digit has been found ; At n - 1 , check if current digit and starting digit are the same then no need to calculate this answer . ; Else find the answer ; Function to find the required count ; Setting up the upper bound ; calculating F ( R ) ; Setting up the upper bound ; calculating F ( L - 1 ) ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE ll K ; ll N ; vector < int > v ; ll dp [ 20 ] [ 1000 ] [ 10 ] [ 2 ] [ 2 ] ; void init ( ll x ) { memset ( dp , -1 , sizeof ( dp ) ) ; v . clear ( ) ; while ( x > 0 ) { v . push_back ( x % 10 ) ; x /= 10 ; } reverse ( v . begin ( ) , v . end ( ) ) ; N = v . size ( ) ; } ll fun ( ll pos , ll sum , ll st , ll check , ll f ) { if ( pos == N ) { return ( sum == 0 and check == 1 ) ; } if ( dp [ pos ] [ sum ] [ st ] [ check ] [ f ] != -1 ) return dp [ pos ] [ sum ] [ st ] [ check ] [ f ] ; ll lmt = 9 ; if ( ! f ) lmt = v [ pos ] ; ll ans = 0 ; for ( int digit = 0 ; digit <= lmt ; digit ++ ) { ll nf = f ; ll new_sum = ( sum + digit ) % K ; ll new_check = check ; ll new_st = st ; if ( f == 0 and digit < lmt ) nf = 1 ; if ( check == 0 and digit != 0 ) { new_st = digit ; new_check = 1 ; } if ( pos == N - 1 and new_st == digit ) continue ; ans += fun ( pos + 1 , new_sum , new_st , new_check , nf ) ; } return dp [ pos ] [ sum ] [ st ] [ check ] [ f ] = ans ; } void findCount ( int L , int R , int K ) { init ( R ) ; ll r_ans = fun ( 0 , 0 , 0 , 0 , 0 ) ; init ( L - 1 ) ; ll l_ans = fun ( 0 , 0 , 0 , 0 , 0 ) ; cout << r_ans - l_ans ; } int main ( ) { ll L = 10 ; ll R = 20 ; K = 2 ; findCount ( L , R , K ) ; return 0 ; }