Similars

2015 TCO 1A · 2015-04-08 · by subscriber

2015 TCO 1A · 2015-04-08 · by subscriber · Brute Force, Simple Search, Iteration

Show categories

Class Name: Similars

Return Type: int

Method Name: maxsim

Arg Types: (int, int)

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.

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

Submissions are judged against all 147 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Similars with a public method int maxsim(int L, int R) · 147 test cases · 2 s / 256 MB per case