Topcoder TCO’21 Round 2B – Combinatorics problem

Problem link:  Alternate Odd Even

Problem summary:

Find the K’th number from a positive increasing sequence of numbers such that their digits in a number alternate being odd and even.

Key facts:

1. Any digit from 1-9 can sit at the Most Significant Bit (MSB) position. For all other position, the number of digits that can sit there is always 5. Those 5 digits come from two disjoint lists. List1 = [0, 2, 4, 6, 8] or List2 = [1, 3, 5, 7, 9]
2. From fact 1 we can deduce that, the number of unique numbers that can be generated having d digits is: 9*5^(d-1)

My Approach:

First, find the number of digits that the K’th number will have:

It is smallest d such that

Let’s define N based on the d we just defined:

It is now evident that, the N’th smallest number having d digits is the answer of our problem. Now the question is: how do we find the N’th smallest suitable number having d digits? We can start iteratively starting from MSB (position d-1, LSB position is 0). In every bit positions we try eligible digits in increasing order and see how many numbers we can make with i’th position containing a digit say 4. The purpose of this calculation is to identify a digit in every i’th position such that our N’th smallest number will definitely have that number.

My code during the contest and it passed system test.