DistinctDigits
SRM 426 · 2008-11-22 · by StevieT
SRM 426 · 2008-11-22 · by StevieT · Brute Force, Math, Search
Problem Statement
Problem Statement
Consider the set of numbers formed by taking every number between low and high, inclusive, and sorting the digits of each number in non-increasing order (the numbers are initially written without any extra leading zeros). Return the number of distinct numbers in this new set.
Constraints
- high will be between 1 and 100,000,000 (10^8), inclusive.
- low will be between 1 and high, inclusive.
Examples
0)
1 20 Returns: 20
All of the integers between 1 and 20 have distincts sets of digits.
1)
1 30 Returns: 29
"21" has the same digits as "12" when sorted. All the rest are still distinct.
2)
151 309 Returns: 98
3)
1 15000 Returns: 1641
4)
153697 154689 Returns: 318
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DistinctDigits with a public method int count(int low, int high) · 77 test cases · 2 s / 256 MB per case