O(1) with explanation


  • 0
    A

    It is obvious that there can't exist number with unique digits with more than 10. So, its not necessary to count for n more than 10.While generating number's digits, in each step the quantity of available digits decreases by 1. The multiplication of available digits for each prefix gives us all possible variants for length n. However we need to calculate all possible variants for all length from i till n we need to sum up all the prefix's variants.

    public class Solution {
        public int countNumbersWithUniqueDigits(int n) {
            if (n==0) return 1;
            n = Math.min(10, n);
            int variants = 10;
            int cur = 9;
            for (int i=1; i<n; i++) {
                cur*=(10-i);
                variants+=cur;
            }
            return variants;
        }
    }
    

Log in to reply
 

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