The n-th Number with Odd Digits
National Olympiad — Municipal round (2019 season)
Submission name: odd.cpp
Problem summary
List positive numbers containing only 1,3,5,7,9 in increasing order and find the n-th member, counting from 1.
Input
Positive rank n.
Output
The n-th odd-digit number.
Constraints
1 ≤ n < 100000.
Worked example
Input and output for the worked example discussed below.
Input
7
Output
13
Solution analysis
- Numeric order is length order followed by lexicographic digit order. Regard the five allowed digits as symbols of bijective base 5.
- Repeatedly subtract one, map the remainder modulo 5 to a digit in 13579, and divide by 5. Reverse the collected digits at the end.
- Rank 7 gives digit 3 after the first subtraction, then digit 1, producing 13. Repeating the subtraction at each step handles boundaries between lengths.
Why it works
Bijective base-5 numerals enumerate all nonempty strings over the five ordered symbols.
Complexity: O(log n) time and O(log n) result space.
Watch out. Ordinary base 5 has an unwanted zero symbol; subtract one before each remainder and reverse the result.
Commented C++17 solution
An independently written complete program with standard headers.
// Bijective base-5 numerals enumerate all nonempty strings over the five ordered symbols.
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int main(){
int rank;
cin>>rank;
string answer;
const string digits="13579";
while(rank>0){
rank--;
answer+=digits[rank%5];
rank/=5;
}
reverse(answer.begin(),answer.end());
cout<<answer<<'\n';
}