概要
二つの整数 A, B について、A <= B * 10 かつ B <= A * 10 を満たすものを「類似数」と呼ぶ。
[ lower, upper ] の範囲から、互いに類似数でないように幾つかの数を選ぶとき、最大でいくつの数を選ぶことができるか。
解法
ある数 a について、a より大きく類似数でない数は a * 10 + 1 を超える数です。
a' = a * 10 + 1 について、a' より大きく類似数でない数は、同様に a' * 10 + 1 を超える数となるので、同じ式を使って、最小の非類似数を求めることができます。
初期値として与える数についてですが、区間のできるだけ左から選ぶことで i 番目に選ばれる数を左に寄せることができるので、lower から始めます。
コード
class TheSimilarNumbers { public: int find( int lower, int upper ) { int res = 0; for ( ; lower <= upper; lower = lower * 10 + 1 ) { res++; } return res; } };
