Make writing a habit together! This is the 10th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

【 brush question diary 】357. Count the number of different numbers

357. The number of different figures in the statistics, medium

I. Title Description:

Brothers, today check loophole a little late, come back to continue to brush the problem, fortunately saw this problem in the morning, have a certain idea, now to have a look at it

2. What ideas does this question examine? What’s your thinking?

The range of digits in the range is left closed and right open. The range of digits in the range is left closed and right open

The maximum range of this number is 10 to the eighth, which is a 1 followed by eight zeros

The title is clear. At first glance, it seems that the idea is not clear

Nothing, we can reason, we understand, this is actually a math problem, remember when we were in high school or junior high school, we solved such a math problem

So we can do the same thing

When n is equal to 3, when you have 3 digits, you have 9 times 9 times 8, which is 648, plus 91, which is 739

In this case, we can see that this is actually a math problem, a permutation and combination problem

Now this math problem can be solved, and then we can translate the code according to the idea

Three, coding

We need to pay attention to that we need to pay attention to the number of different digits above each bit

The encoding is as follows:

func countNumbersWithUniqueDigits(n int) int {
    if n == 0 {
        return 1
    }
    if n == 1 {
        return 10
    }
    // If n is equal to 1, the result is 10, and the current 1 digit is 9, because the first digit of 0-9 cannot start with 0
    res, cur := 10.9
    for i := 0; i < n- 1; i++ {
        // The first digit has 9 kinds, the second digit has 9 kinds, the third digit has 8 kinds, and so on
        cur *= 9 - i
        res += cur
    }
    return res
}
Copy the code

Iv. Summary:

This one has a small amount of code, and the time complexity is easy to see, it’s O(n), the number of cycles is n-1, and the space complexity here is O(1), and we’re introducing constant level space consumption

357. Count the number of different numbers

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~