すべてのチャレンジ
難しい 1件解決済み 正答率100.0%

Count Numbers With Distinct Neighbors

Count range values whose adjacent decimal digits are never equal.

このチャレンジで学べること

  • Count numbers up to a limit digit by digit
  • Track the previous digit and tight bounds
  • Answer a range as f(b) - f(a - 1)

問題

翻訳を表示

Count integers from left through right, including both endpoints, that have no equal neighboring digits. Use their usual decimal writing with no leading zeroes. Zero and all other single-digit numbers qualify.

Implement counting_numbers(left, right).

Input

left: The first allowed value.

right: The last allowed value.

Output

Return how many values satisfy the rule.

制約

0 ≤ left ≤ right ≤ 10¹⁸. The range may be too large to inspect each integer individually.

例

例 1
入力:
left = 10
right = 15

期待される出力:
expected = 5
入力:
long long left = 10;
long long right = 15;

期待される出力:
long long expected = 5;
入力:
long left = 10;
long right = 15;

期待される出力:
long expected = 5;

解説

Only 11 has equal neighboring digits. The other five numbers qualify.

例 2
入力:
left = 0
right = 9

期待される出力:
expected = 10
入力:
long long left = 0;
long long right = 9;

期待される出力:
long long expected = 10;
入力:
long left = 0;
long right = 9;

期待される出力:
long expected = 10;

解説

All ten values have just one digit and therefore no equal neighbors.

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

Count valid numbers up to each endpoint, then subtract to get the range answer.

ヒント 2

Digit DP fits because validity depends on adjacent digits and whether you have started the number.

ヒント 3

Leading zeros need special handling so that shorter numbers are counted correctly.

目安の計算量

O(k * 10 * states) time, O(k * states) extra space

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

# コーダー 言語 時間 メモリ AI 評価 解答
1 ННикита Python 807 ms - 5/5 コードを見る

他の人の解答から学ぶ

コミュニティの解答

ネタバレ注意:下に1件の全解答あり まずは自分で挑戦してみましょう。他の開発者のコードやAIレビューも見ることができます。 サインインして課題を解くと議論に参加できます。