모든 챌린지
어려움 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

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 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.