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.