How many times does a digit appears in all the numbers that are smaller than an n.

Question

Hello, SoloLearn. I was wondering if you can help me with a c++ problem. I must show how many times a digit appears in every number that is smaller than an n.
e.g:n=15, digit=1
answer:8
The digit 1 appears in: 1,10,11(twice),12,13,14,15.

I must use an optimised method(I can't generate all the numbers and see, it takes to much time.).
Thank you for your time.
Goodbye!

Answer 1

This calls for a mathematical solution!
Suppose n = 99, digit = 9 (classic example). Then the numbers that appear are:
9, 19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99.
Can you see a pattern? The number increases by 10 each time, unless the tens digit is 9.
Consider n = 999.
The numbers > 99 that fit are:
109, 119, 129... 189, 190, 191... 199, 209, 219... 899, 900, 901, 902... 999
As we can see, the last 100 numbers qualify. We can see a bigger pattern now...
I think you should know how to go on from here. If you need some now help, feel free to ask. 😉

Answer 2

Thank you for your help blackcat111. I still have 1 question: if i choose n=30 and d=2. The digit 2 appears in 2, 12, 20,21,22,23,24,25,26,27,28,29 even though 2 is not equal to the tens digit 3. I am still trying to figure out how to write it. Thank you very much for your time.

Answer 3

Well, judging from what I think, that case should only arise when n is a number (10a + b) where a > digit and b < digit, where a does not contain the digit and b ≠ digit.
In that case, what I'd do is to check if this condition applies. If it does, the last number would be (10(a-1) + digit) if (a-1) ≠ digit and (10(a-1) + 9) if a-1 == digit.
Sorry if this was a bit mathematical, but I'll try to minimize that next time. Again, feel free to ask if you don't understand anything or if you still need help. 😉