プログラミング：アルゴリズム、数学、データ構造の10進表現で3を持つすべてのそのような数の数を与える

数値nを指定すると、数字3を含まない1からnの数字を10進表現で返す関数を書く

この問題を解決する最も最適な方法は何か。

私は単純な、すなわちnlogn（複雑さを見てアプローチを推測するのは簡単:)で使用しているアプローチ）

回答：

次のアルゴリズムは、10進表現では「3」のない0から（n-1）までの整数である。 （私は1 .. nから0 .. n-1までの間隔を次の計算をわずかに簡略化するために変更しました。）

（私は複雑さの計算の専門家ではないが、私はこのアルゴリズムの複雑さは O(log n)なぜなら、各桁ごとに固定数のステップを実行するからです n。）

第1の観察は、多くてもd桁の整数の数（すなわち、間隔0 .. 10の数字^d-1）は10進数で3の数字を持たず、ちょうど9^dなぜなら、各桁に9つの選択肢0,1,2,4,5,6,7,8,9があるからです。

ここで、5桁の数字n = a₄a₃a₂a₁a₀.

私たちは間隔の小数表現で "3"を持たない整数の数を別々に計算します

• 私₀：a₄a₃a₂a₁ 0 <= i <a₄a₃a₂a₁a₀
• 私₁：a₄a₃a₂ 0 0 <= i <a₄a₃a₂a₁ 0
• 私₂：a₄a₃ 0 0 0 <= i <a₄a₃a₂ 0 0
• 私₃：a₄ 0 0 0 0 <= i <a₄a₃ 0 0 0
• 私₄：0 0 0 0 0 <= i <a₄ 0 0 0 0

区間Iにおける整数の数_j 10進表記で「3」を持たない

• 0の場合、上位の数値の1つがa_{j + 1}、a_{j + 2}、...は3に等しく、 さもないと：
• a_j * 9^j、0 <= aの場合_j <= 3、（a_j の選択肢 j^th 小数点以下桁すべてに対して9つの選択肢）、
• （a_j - 1）* 9^j、aj> 3の場合（3はjの有効な選択肢ではないため^th 数字）。

したがって、次のような機能があります。

/*
* Compute number of integers x with 0 <= x < n that do not
* have a 3 in their decimal representation.
*/
int f(int n)
{
int count = 0;
int a;      // The current digit a_j
int p = 1;  // The current value of 9^j

while (n > 0) {
a = n % 10;
if (a == 3) {
count = 0;
}
if (a <= 3) {
count += a * p;
} else {
count += (a-1) * p;
}
n /= 10;
p *= 9;
}

return count;
}