Tất cả thử thách
Khó 1 đã giải Tỷ lệ chấp nhận 100.0%

Count Numbers With Distinct Neighbors

Count range values whose adjacent decimal digits are never equal.

Bạn sẽ học được gì

  • 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)

Đề bài

Xem bản dịch

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.

Ràng buộc

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

Ví dụ

Ví dụ 1
Đầu vào:
left = 10
right = 15

Kết quả mong đợi:
expected = 5
Đầu vào:
long long left = 10;
long long right = 15;

Kết quả mong đợi:
long long expected = 5;
Đầu vào:
long left = 10;
long right = 15;

Kết quả mong đợi:
long expected = 5;

Giải thích

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

Ví dụ 2
Đầu vào:
left = 0
right = 9

Kết quả mong đợi:
expected = 10
Đầu vào:
long long left = 0;
long long right = 9;

Kết quả mong đợi:
long long expected = 10;
Đầu vào:
long left = 0;
long right = 9;

Kết quả mong đợi:
long expected = 10;

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 807 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.