Java simple code O(1) space O(n) time with combinatorics knowledge


  • 7

    test case is wrong when n==1, it should be 11 instead of 10, from 0 to 10 inclusively

    n=2 10+9 * 9

    n=3 10+9 * 9+9 * 9 * 8

    n=4 10+9 * 9+9 * 9 * 8+9 * 9 * 8 * 7

    ...

    when n > 10, the total number won't increase any more, so we set n=10 in that case

    public class Solution {
        public int countNumbersWithUniqueDigits(int n) {
            if (n == 0) {
                return 2;
            }
            if (n == 1) {
                return 10; // should be 11
            }
            n = Math.min(n, 10);
            int sum = 10;
            int tmp = 9;
            for (int i = 1; i < n; i++) {
                tmp *= 10 - i;
                sum += tmp;
            }
            return sum;
        }
    }

  • 0
    J

    Now the condition changed to exclude 10^n


  • 0

    @xuyirui same idea here to use combination calculations, here's one that is a bit more explicit.

        public int CountNumbersWithUniqueDigits(int n) 
        {
            int total = 0;
            if (n > 10) n = 10;
            for (int i = 0; i <= n; i++) total += CountAt(i);
            return total;
        }
        
        public int CountAt(int digits)
        {
            switch (digits)
            {
                case 0  : return 1;
                case 1  : return 9;
                case 2  : return 9 * 9;
                case 3  : return 9 * 9 * 8;
                case 4  : return 9 * 9 * 8 * 7;
                case 5  : return 9 * 9 * 8 * 7 * 6;
                case 6  : return 9 * 9 * 8 * 7 * 6 * 5;
                case 7  : return 9 * 9 * 8 * 7 * 6 * 5 * 4;
                case 8  : return 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3;
                case 9  : return 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2;
                case 10 : return 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;
                default : return 0;
            }
        }
    

Log in to reply
 

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