整数でXが現れる回数(C++)

タイトル:
与えられたnについて,1−nの範囲内でXが出現する回数を求める.(0 <= X <= 9)
考え方:
この問題nlognのアルゴリズムは考えやすい.
1-nの各数を巡り、各数の各ビットが1であるか否かを判断し、カウントすればよい.
次のコードを直接示します.

#include <iostream>

using namespace std;

int NumberOf1Between1AndN(int n, int x)
{
	int cnt = 0;

	for(int i = 1; i <= n; ++i)
	{
		int temp = i;

		while(temp)
		{
			if(temp % 10 == x)
			{
				cnt++;
			}
			temp /= 10;
		}
	}

	return cnt;
}

int main(void)
{
	int n, x;
	cin>>n>>x;

	cout<<NumberOf1Between1AndN(n, x)<<endl;

	return 0;
}

この問題については,複雑度O(logn)の解法も存在する.
【注:この解法は、分析X 1<=X<=9ともに成立する】以下に共通の考え方を示す.
大まかな考え方は以下の通りである.
まず、
1〜10桁のXが1回出現した.
1-100 10桁のXが10回現れた.
1-1000百桁Xが100回出現した.
次のようにします.
1-10^i次高位数(右からi番目のビットが1番目)Xが10^(i-1)回現れる
n=3672 X=6を例として説明する.
まず,ビット上Xの個数を統計する.【1-3670桁が6の367桁残りの3671 3672桁が6であるはずがない】――367
次に10桁でXの個数を集計する.【1-3600桁が6の36*10=360個残りの3601-3672桁が6の個数10(7>6)】——370
その後、100ビットのXの個数を統計します.【1-3000百桁6の合計3*100=300残りの3001-3672十桁6の個数72+1=73(3600-3672)】——373
最後に千位でXの個数を統計する.【千位では3<6なので千位では6の数は存在しない】
したがって、合計367+370+373です.
まとめ:
i位左(高位)の数字をとり,10^(i−1)を乗じて基礎値aを得る.i番目の数字をとり、補正値を算出する.i番目の数字がXより大きい場合、結果はa+10^(i−1)となる.i番目の数字がXより小さい場合、結果はaである.i番目の数字がXに等しい場合は、i番目の右(下位)の数字をbとし、最終結果はa+b+1とする.
コード:

#include <iostream>

using namespace std;

//      X   1-n       
int count(int n, int x)
{
	int cnt = 0, k;

	// k = n / i = 0             
	for (int i = 1; k = n / i; i *= 10)
	{
		cnt += (k / 10) * i;

		int cur = k % 10;
		if (cur > x)
		{
			cnt += i;
		}
		else if(cur == x)
		{
			cnt += (n - k * i + 1);
		}
	}


	return cnt;
}

int main(void)
{
	int n;
	cin>>n;

	cout<<count(n, 1)<<endl;

	return 0;
}

ただし、上記コードはX=0の場合には適用されません.【1桁の最高位が0にならないため】
上記のコードを少し修正するとX=0の個数を統計できます.
コード:

#include <iostream>

using namespace std;

//      0   1-n       
int count(int n, int x)
{
	int cnt = 0, k;

	// k = n / i = 0             
	for (int i = 1; (k = n / i) / 10; i *= 10)
	{
		cnt += (k / 10) * i;

		if (k % 10 == 0)
		{
			cnt += (n - k * i + 1 - i);
		}
	}

	return cnt;
}

int main(void)
{
	int n;
	cin>>n;

	cout<<count(n, 0)<<endl;

	return 0;
}

上記の2つのコードを結合すると、次のようになります.

#include <iostream>

using namespace std;

//      0   1-n       
int count(int n, int x)
{
	int cnt = 0, k;

	// k = n / i = 0             
	for (int i = 1; k = n / i; i *= 10)
	{
		//      
		int highNum = k / 10;

		//   0
		if (x == 0)
		{
			if (highNum != 0)
			{
				highNum--;
			}
			else
			{
				break;
			}
		}

		cnt += highNum * i;

		int cur = k / 10;
		if (cur > x)
		{
			cnt += i;
		}
		else if (cur == x)
		{
			cnt += n - k * i + 1;
		}
	}

	return cnt;
}

int main(void)
{
	int n, x;
	cin>>n>>x;

	cout<<count(n, x)<<endl;

	return 0;
}