Similars | Topcoder Archive

Problem Statement

Given two positive integers x and y, their similarity S(x, y) is defined as follows: To compute S(x, y) we count all d between 0 and 9, inclusive, such that both x and y contain the digit d when written in base 10 (without any leading zeros). For example, S(1123, 220181) = 2 since both numbers contain the digit 1 and both contain the digit 2.

You are given two ints L and R that define a range. Find two distinct integers in this range that have the largest similarity. Formally, return the maximum of S(a, b) over all a, b such that L <= a < b <= R.

Definition

Class:: Similars
Method:: maxsim
Parameters:: int, int
Returns:: int
Method signature:: int maxsim(int L, int R)
(be sure your method is public)

Constraints

R will be between 2 and 100,000, inclusive.
L will be between 1 and R - 1, inclusive.

Examples

```
1
```
```
10
```
```
Returns: 1
```
We have S(1, 10) = 1 since both numbers contain the digit 1. All other pairs of numbers within this range have similarity 0.
```
1
```
```
99
```
```
Returns: 2
```
There are many pairs with similarity 2, for example pairs (23,32) and (38,83).
```
99
```
```
100
```
```
Returns: 0
```
Here we have only one pair (99, 100) and its similarity is 0.
```
1000
```
```
1010
```
```
Returns: 2
```
```
444
```
```
454
```
```
Returns: 2
```

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.