SmoothMultiples | Topcoder Archive

Problem Statement

A positive integer is K-smooth if each pair of its consecutive digits differs by at most K.

For example:

7, 77, and 333 are all 0-smooth while 12 and 20 are not.
7, 77, 234, 1010, 4323, and 556566765454 are all 1-smooth while 42, 90, and 54222 are not.
7, 42, 1357, 86420, and 865454321001 are all 2-smooth while 36, 204, and 9090 are not.

Count all K-smooth integers that lie between A and B, inclusive, and are multiples of C.

Definition

Class:: SmoothMultiples
Method:: count
Parameters:: int, long, long, long
Returns:: long
Method signature:: long count(int K, long A, long B, long C)
(be sure your method is public)

Constraints

K will be between 0 and 9, inclusive.
A will be between 1 and 10^11 - 1, inclusive.
B will be between A and 10^11 - 1, inclusive.
C will be between 1 and 10^11 - 1, inclusive.

Examples

```
1
```
```
10
```
```
33
```
```
1
```
```
Returns: 8
```
We are counting all 1-smooth integers in the range [10,33]. There are eight of them: 10, 11, 12, 21, 22, 23, 32, and 33.
```
1
```
```
97
```
```
102
```
```
1
```
```
Returns: 4
```
The 1-smooth integers in this range are 98, 99, 100, and 101.
```
1
```
```
97
```
```
102
```
```
2
```
```
Returns: 2
```
The even 1-smooth integers in this range are 98 and 102.
```
9
```
```
123
```
```
45678
```
```
3
```
```
Returns: 15186
```
All positive integers are 9-smooth. There are 15,186 multiples of three in the given range.
```
3
```
```
1234
```
```
5678
```
```
73
```
```
Returns: 13
```
These are the 13 numbers: 1241, 1314, 2336, 2555, 3212, 3358, 3431, 3577, 4234, 4453, 4745, 5256, and 5475.
```
0
```
```
123
```
```
4567
```
```
1
```
```
Returns: 12
```
These are the 12 numbers: 222, 333, ..., 999, 1111, 2222, 3333, and 4444.
```
9
```
```
3
```
```
99999999995
```
```
1
```
```
Returns: 99999999993
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.