LittleElephantAndSubset
SRM 597 · 2013-06-25 · by Witaliy
Problem Statement
Little Elephant from the Zoo of Lviv has a set S. The set S contains the integers 1, 2, 3, ..., N. He considers some non-empty subset of S cool if we can write down all elements of the subset by using each of the digits 0-9 at most once.
Examples: The subsets {12,345,67890} and {47,109} are cool. The subset {147,342} is not cool because the digit 4 is used twice. The subset {404} is not cool for the same reason.
You are given the
Constraints
- N will be between 1 and 1,000,000,000 (10^9), inclusive.
3 Returns: 7
All 7 non-empty subsets are cool in this case: {1, 2, 3} {1, 2} {1, 3} {2, 3} {1} {2} {3}
10 Returns: 767
In this case, the total number of non-empty subsets is 2^10-1 = 1023. The only not cool subsets are those that contain both 1 and 10. There are 2^8 = 256 of them. Thus, the answer is 1023-256 = 767.
47 Returns: 25775
4777447 Returns: 66437071
1000000000 Returns: 88291951
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LittleElephantAndSubset with a public method int getNumber(int N) · 55 test cases · 2 s / 256 MB per case