문제
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.
예시
입력:
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.
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.