3966. Count Good Integers in a Range
Description
You are given three integers l, r and k.
A number is considered good if the absolute difference between every pair of adjacent digits is at most k.
Return the number of good integers in the range [l, r] (inclusive).
The absolute difference between values x and y is defined as abs(x - y).
Example 1:
Input: l = 10, r = 15, k = 1
Output: 3
Explanation:
- The good integers in the range are 10, 11, and 12.
- For 10,
abs(1 - 0) = 1. - For 11,
abs(1 - 1) = 0. - For 12,
abs(1 - 2) = 1. - All these differences are at most
k = 1. Thus, the answer is 3.
Example 2:
Input: l = 201, r = 204, k = 2
Output: 2
Explanation:
- The good integers in the range are 201 and 202.
- For 201,
abs(2 - 0) = 2andabs(0 - 1) = 1. - For 202,
abs(2 - 0) = 2andabs(0 - 2) = 2. - Thus, the answer is 2.
Constraints:
10 <= l <= r <= 10150 <= k <= 9
Solutions
Solution 1
Thinking
\(l\) and \(r\) reach \(10^{15}\), so we cannot list integers. A good number has adjacent digits differing by at most \(k\) — a digit-DP constraint.
Count \([0,r]\) minus \([0,l-1]\). The state stores position, previous digit, tightness, and leading-zero. A new digit must differ from the previous by at most \(k\) once leading zeros have ended.
This directory has no implemented solution yet; the walkthrough stops at that digit DP.
1 | |
1 | |
1 | |
1 | |