Total numbers with no repeated digits in a range | C ++ implementation of above idea ; Maximum ; Prefix Array ; Function to check if the given number has repeated digit or not ; Traversing through each digit ; if the digit is present more than once in the number ; return 0 if the number has repeated digit ; return 1 if the number has no repeated digit ; Function to pre calculate the Prefix array ; Traversing through the numbers from 2 to MAX ; Generating the Prefix array ; Calclute Function ; Answer ; Driver code ; Pre - calculating the Prefix array . ; Calling the calculate function to find the total number of number which has no repeated digit
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MAX = 1000 ; vector < int > Prefix = { 0 } ; int repeated_digit ( int n ) { unordered_set < int > a ; int d ; while ( n != 0 ) { d = n % 10 ; if ( a . find ( d ) != a . end ( ) ) return 0 ; a . insert ( d ) ; n = n / 10 ; } return 1 ; } void pre_calculation ( int MAX ) { Prefix . push_back ( repeated_digit ( 1 ) ) ; for ( int i = 2 ; i < MAX + 1 ; i ++ ) Prefix . push_back ( repeated_digit ( i ) + Prefix [ i - 1 ] ) ; } int calculate ( int L , int R ) { return Prefix [ R ] - Prefix [ L - 1 ] ; } int main ( ) { int L = 1 , R = 100 ; pre_calculation ( MAX ) ; cout << calculate ( L , R ) << endl ; return 0 ; }