5

I have to find out number of integers that have every digit $(0-9)$ in it where integer starting with zero doesn't count i.e leading zero shouldn't be there. So this makes the length of an integer $ \ge 10$.

For eg - for $10$ length $1234567890,9876543201,4567891023$ and so on

For 11 length = $12345678900, 12345678009$ and so on..

For $19$ length =$1122334556677889900,99887766554433220011$ and so on..

Now given a range $L,R$ I need to find out how many such integers falls in between them. Now I was trying out all combinations and checking if it lies within range. Is there a way to apply permutation and combination to do so efficiently and smartly ?

S.H.
  • 51
  • Perhaps you need to construct a recurrence relation , with intial condition : $a_9=8\cdot 8!$ – Jaideep Khare Apr 10 '17 at 15:32
  • Inclusion-exclusion would work, by calculating the number of integers of length $n$ that use only a set of $k < 10$ digits and subtracting from $9 \times 10^{n-1}$; the resulting expressions would be nasty, though. – Connor Harris Apr 10 '17 at 15:36
  • @JaideepKhare Can you elaborate on it ? – S.H. Apr 10 '17 at 15:38
  • @ConnorHarris What will be the expression ? And how do we check if they are between $[L,R]$ – S.H. Apr 10 '17 at 15:40
  • @S.H. If I would have been able to do so, shouldn't I have written an answer yet? xD. I am trying to construct recurrence relation. If I succed, I will definitely write an answer. – Jaideep Khare Apr 10 '17 at 15:40
  • @JaideepKhare Thanks. I am also trying to think along that line. – S.H. Apr 10 '17 at 15:41
  • @S.H. I can give you a bonus problem ^_^
    Suppose you have $a_0, a_1, a_2,..., a_9$. You need to count how many number in $[L,R]$ have exactly $a_0$ 0's, $a_1$ 1's ...., $a_9$ 9's .. Can you solve this? -______-     – Rezwan Arefin Apr 11 '17 at 12:29
  • Perhaps you could clarify what you mean by "range". Are you referring to number length range or simply range of numbers? I had assumed in my (now deleted) answer that you were talking about number length but an unexplained down vote forced me to reconsider. If you mean range of numbers then this is a tricky problem indeed. – N. Shales Apr 11 '17 at 13:37
  • 1
    @N.Shales I think he said range of numbers not range of number of digits ! – Rezwan Arefin Apr 11 '17 at 13:39
  • Thank you @RezwanArefin, I guess that is how everyone here has interpreted it. I suppose that must have been why I got the down vote. – N. Shales Apr 11 '17 at 13:49

0 Answers0