algorithm - 数値 n が与えられたとき、範囲 0...n に 2 桁の数値がいくつあるかを調べます

Question

面接の質問です。

数値 n が与えられたとき、範囲 0...n に 2 桁の数値がいくつあるかを調べます

例えば ​​、

入力 = 13 出力 = 2 (2 と 12)

私は通常の O(n^2) ソリューションを提供しましたが、より良いアプローチがあります。

すぐに答えを得るのに役立つ「トリック」の公式はありますか

Answer 1

数字の 2 を含まない数を数えます。10 ^k未満の数の中には、ちょうど 9 ^kの数があります。^{次に、10 k}からまでの数値を処理する必要がありますn。ここで、

10^k <= n < 10^(k+1)

これは、最初の数字を個別に処理することで実行できます (ケース 2 とその他を区別する必要があります)。次に、最初の 2 桁などを処理します。

たとえば、 の場合、 1000 未満の数字 2 のない数字n = 2345があることがわかります9^3 = 729。1000 から 1999 までの範囲には、このような数字が 729 個あります。次に、2000 から 2345 までの範囲には、何もなく、合計で 1458 になります。したがって、数字の 2 を含む数は

2345 - 1458 = 887

Answer 2

引数「数字」は数えたいもので、引数「数字」は数えたいところまでです。例: '1' の出現回数を 0 から 12 までカウントしたい場合、数字 = 1、数値 = 12 で関数を呼び出すと、'1' の出現回数が返されます。

int countOccurrences(int digit, int number)
{
    int counter = 0;
    for(int i=1; i<number; i++)
    {
        int j = i;
        while(j > 0)
        {
            if(j%10 == digit)
                counter++;
            j /= 10;
        }
    }
    return counter;
}

Answer 3

ABCDEFの数字が付いた数を指定すると、範囲内の「2」の数を数え、[0,F], [0,E9], [0,D99], [0,C999], [0,B9999]それら[0,A99999]を追加できます。

次に、範囲[0, X9999...999]の場合、最上位の数値は。T = X9999...999と書くことができます(X+1) * 10<sup>nines</sup> -1。

その範囲の「2」の数は次のとおりです。

((X >= 2 ? 1/(X + 1)) : 0) + nines/10 ) * (T + 1);

つまり、の場合X >= 2、9+1の位置に「2」がある数の割合はです1/(X+1)。合計(T+1)/(X+1)でその位置に「2」があります。の場合X < 2、[0..T]の数字のその位置に「2」はありません。

1/10他の桁の位置については、すべての桁の位置に「2」があることが簡単にわかります。したがって(T+1)/10、位置0に(T+1)/10「2」、位置1に「2」などがあります。合計で(T+1) * nines / 10。

このソリューションの複雑さはO（logN）です。

Answer 4

これが私の最初のドラフト（Pythonコード）のコーディングに取り掛かる方法です

def count2(n) :
    return [p for p in range(n+1) if '2' in str(p)]

これにより、含まれている番号のリストが返されます。

パフォーマンスに関しては、それほど悪くはありません。n= 10,000,000の場合、平均反復には約5.5秒かかります。