没有数字小于无重复位的给定数量的 [英] No of numbers less than a given number with no repeating digits

问题描述

我们如何才能找到它的数字小于没有重复数字的给定数量的多少？

How can we find the number of numbers less than a given number with no repeating digits in it?

例如这样的数字小于100的数量为90（11，22，33,44，55,66,77,88,99都重复位，因此被排除在外）。

For example the number of such numbers less than 100 is 90. (11, 22, 33,44, 55,66,77,88,99 have repeating digits so are excluded).

类似地，对于小于1000，数字像101，110，122，202等必须被排除。

Similarly for less than 1000, digits like 101, 110, 122, 202 etc have to be excluded.

推荐答案

您可以考虑两种情况：

• 数超过极限短
• 数字是从限制不同，在一些数字

的计数ð位数字编号为 9 * 9 * 8 * ... = 9 * 9！/（9-D） ！（第一个数字可能不是零）。比 D 更短的所有数字的计数为0位数字的计数+ .. D-1的数 - 数位数字。这些款项可能是precomputed（甚至硬codeD）。

The count of d-digit numbers is 9*9*8*... = 9*9!/(9-d)! (the first digit may not be zero). The count of all numbers shorter than d is the count of 0-digit numbers + .. count of d-1-digit numbers. These sums may be precomputed (or even hard-coded).

D 位半数字与 F的第一个数字的计数给出的（10 -f）* ... *（10-（D-1））=（10-f）的！/（10-d）中<！/ code>。您可以precomupte的阶乘为好。

The count of d-digit numbers with f first digits given is (10-f)*...*(10-(d-1)) = (10-f)!/(10-d)!. You can precomupte the factorials as well.

伪code：

To precompute fac:
  - fac = int[10];
  - fac[0] = 1;
  - for i in 1..10:
    - fac[i] = fac[i-1] * i;

To precompute count_shorter:
  - cs = int[10];
  - cs[0] = 0;
  - cs[1] = 1; // if zero is allowed
  - for i in 1..10:
    - cs[i+1] = cs[i] + 9 * fac[9] / fac[10-i]
  - count_shorter = cs;

To determine the count of numbers smaller than d:
  - sl = strlen(d)
  - if sl > 10
    - return count_shorter[11]
  - else
    - sum = 0
    account for shorter numbers:
    - sum += count_shorter[sl]
    account for same-length numbers; len=count of digits shared with the limit:
    - sum += 9* fac[9] / fac[10-sl];
    - for every len in 1..{sl-1}:
      count the unused digits less than d[len]; credits to @MvG for noting:
      - first_opts = d[len]-1;
      - for every i in 0..{len-1}:
        - if d[i] < d[len]
          - first_opts -= 1;
      - sum += first_opts * fac[9-len] / fac[10-sl] 
  - return sum

这篇关于没有数字小于无重复位的给定数量的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！