### PROBLEM LINK:

**Author:** Prateek Gupta

**Testers:** Istvan Nagy

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

Easy

### PREREQUISITES:

finding pattern, base 5 representation, simple maths

### PROBLEM:

A number n is called a *magical* number if the sum of product of individual digits (in base 10 representation) of each subsequence of digits is even. You have to find K-th *magical* number.

### QUICK EXPLANATION:

A number n will be *magical* number, iff all of its digits are even. Represent K in base 5, and the corresponding number with each digit 0 \leq i < 5 being mapped to 2 * i will be the K-th *magical* number.

### EXPLANATION:

**Properties of a magical number**

**Lemma:**A number will be

*magical*number, if all of its digits in decimal representation are even.

**Proof**: You can observe this property by finding a pattern by writing a bruteforce solution for small numbers. A more formal proof follows.

Note that the order of digits of n does not matter. Product of digits of subsequence containing only even digits will be even. Similarly, a subsequence containing any even digit will be even. Now, all the subsequences that remain are the ones which consist of all odd digits. Sum of each such subsequence will be odd. Number of such subsequences will be 2^o - 1 where o denotes number of odd digits in n. Note that 2^o - 1 will be odd if o is non-zero. Hence if a number contains even a single odd digit, sum of product of digits of subsequences will be odd.

**Finding K-th number**

Note that you can view magical numbers in decimal representation as numbers written in base 5 representation, where a digit i in base 5 has the value of 2 * i (which will be an even number) in decimal, e.g. 2480 (decimal) can be thought 1240 (in base 5).

Finding K-th number in base 5, is same as representing K - 1 in base 5. You can find the corresponding magical number in decimal representation by replacing each digit i by 2 * i.

**Example**

Assume we have to find K = 10-th magical number.

Write K - 1 in base 5, K - 1 = 9 = (14)_5.

Now replace digit i, with 2 * i, i.e. (28)_{10}.

Therefor, 10-th magical number will be 28.

### Time Complexity:

\mathcal{O}(log_5^{K}) - Represent K in base 5.