share two C++ solutions iteration and combinatorics with comments


  • 0
    B
        // solution 1 iteration
        // T(i): unique numbers in [10^(i-1), 10^(i)] -- currUniqueNums
        // U(i): nonunique numbers in [10^(i-1), 10^(i)] -- nonUniqueNums
        // U(i) = T(i-1)*i + U(i-1) *10  
        // T(i)= [10^(i-1), 10^(i)]-U(i)
        int countNumbersWithUniqueDigits(int n) {
            if(n==0)    return 1;
            if(n==1)    return 10;
            // start from n=2
            int totalNums=91, currUniqueNums=81, nonUniqueNums=9, rangeExt=900; // 10~99
            for(int i=2;i<n;i++, rangeExt*=10){
                nonUniqueNums=currUniqueNums*i+nonUniqueNums*10; // U(i) = T(i-1)*i + U(i-1) *10 
                currUniqueNums=rangeExt-nonUniqueNums; // T(i)= [10^(i-1), 10^(i)]-U(i)
                totalNums+=currUniqueNums;
            }
            return totalNums;
        }
        
        // solution 2 combinatorics
        int countNumbersWithUniqueDigits(int n) {
            if(!n)  return 1;
            // start from n=1
            int res=10;
            // the highest digit could be 1~9 and all other n-1 digits are permutation(9, n-1) 
            // so the total number of combinations are 9*permutation(9, n-1)
            for(int i=9, j=9;i>9-(n-1);i--, j*=i)   // j is Permutation(9, n-1)
                res+=9*j;
            return res;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.