Java, O(1), with explanation


  • 51
    A

    This is a digit combination problem. Can be solved in at most 10 loops.

    When n == 0, return 1. I got this answer from the test case.

    When n == 1, _ can put 10 digit in the only position. [0, ... , 10]. Answer is 10.

    When n == 2, _ _ first digit has 9 choices [1, ..., 9], second one has 9 choices excluding the already chosen one. So totally 9 * 9 = 81. answer should be 10 + 81 = 91

    When n == 3, _ _ _ total choice is 9 * 9 * 8 = 684. answer is 10 + 81 + 648 = 739

    When n == 4, _ _ _ _ total choice is 9 * 9 * 8 * 7.

    ...

    When n == 10, _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

    When n == 11, _ _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 0 = 0

    public static int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        int ans = 10, base = 9;
        for (int i = 2; i <= n && i <= 10; i++) {
            base = base * (9 - i + 2);
            ans += base;
        }
        return ans;
    }

  • 1
    A

    Hi, this may be late but I am wondering when n=2 why is it 9* 9 and not 9*8? Because you said that you exclude the already chosen one so shouldn't the number of digits you have to work with be 1 less? I am just trying to understand for the sake of my understanding, thank you very much!


  • 3
    A

    0 can't be put in first first position, but 0 can be put in other positions. It's because of 0.


  • 2
    L

    The explanation is quit clear. The only thing is the for loop conditions is not that straight forward. I made a little bit change based on your solution. See detail below:

    public int countNumbersWithUniqueDigits(int n) {
        if(n==0) return 1;
        if(n==1) return 10;
    
        int ans = 10, base = 9;
        //i: next multi-factor, j: control loop count
        for(int i=9, j=n-1; i>0 && j>0; i--, j--) {
            base *= i;
            ans +=base;
        }
        return ans;
    }
    
        public static void main(String[] args) {
            CountNumbersWithUniqueDigits slu = new CountNumbersWithUniqueDigits();
            Assert.assertTrue("0", slu.countNumbersWithUniqueDigits(0), 1);
            Assert.assertTrue("1", slu.countNumbersWithUniqueDigits(1), 10);
            Assert.assertTrue("2", slu.countNumbersWithUniqueDigits(2), 9*9 + 10);
            Assert.assertTrue("3", slu.countNumbersWithUniqueDigits(3), 9*9*8 + 9*9 + 10);
            Assert.assertTrue("4", slu.countNumbersWithUniqueDigits(4), 9*9*8*7 + 9*9*8 + 9*9 + 10);
            Assert.assertTrue("5", slu.countNumbersWithUniqueDigits(5), 9*9*8*7*6 + 9*9*8*7 + 9*9*8 + 9*9 + 10);
        }
    

  • 4

    @laqxs LOL, yours is so damn "straight forward".

    I think mine is much "straight forward" than yours:

    if (n==0) return 1;
    else if (n==1) return 10;
    else if (n==2) return 91;
    else if (n==3) return 739;
    else if (n==4) return 5275;
    else if (n==5) return 32491;
    else if (n==6) return 168571;
    else if (n==7) return 712891;
    else if (n==8) return 2345851;
    else if (n==9) return 5611771;
    return 8877691;
    

    :-)


  • 0
    L

    @zhugejunwei
    The "straightforward" I mentioned is for loop below not the testing main() method. You can skip the main() method.

        for(int i=9, j=n-1; i>0 && j>0; i--, j--) {
            base *= i;
            ans +=base;
        }
    

  • 0

    @laqxs I was just kidding. )


  • 0
    S

    very similar to yours
    Let f(k) = count of numbers with unique digits with length equals k.

    f(1) = 10
    f(2) = 9 * 9= 81 2 digits
    f(3) = 9 * 9 * 8
    f(4) = 9 * 9 * 8 * 7
    ....

    public class Solution {

    public int countNumbersWithUniqueDigits(int n) {
        if (n==0)
            return 1;
        int sum  =10;
        int q = 9;
        for (int i =1; i<n; i++){
            q *= (10-i);
            sum += q;
        }
        
        return sum;
    }
    

    }


  • 0
    C

    @zhugejunwei
    interesting


Log in to reply
 

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