DIFFICULTY:
Easy
PREREQUISITES:
Number-System
PROBLEM:
A number with all digits even is a “Leg-Strong Number”. You need to print the kth “Leg-Strong Number”, 0 being the first such number.
QUICK EXPLANATION:
Subtract k by 1. Express the resulting value of k in base-5 number system. Now multiply resulting base-5 number by 2. The resulting number is the answer to the question.
EXPLANATION:
Since a “Leg-Strong” number can only consist of numbers from the set {0,2,4,6,8}. This set consists of 5 possible even numbers.
Recall that a binary system is expressed as base-2 system because it can have only 2 possible digits(0 and 1). A base-3 system can have only 3 possible digits(0,1 and 2). Similarly a base-5 system can have 5 possible digits (0,1,2,3 and 4).
We have 0,2,4,6,8 in our set but a base-5 system can have 0,1,2,3,4. So we can multiply any digit from {0,1,2,3,4} to get a digit in {0,2,4,6,8}. Now since the numbering starts from 1 we need to subtract 1 from k. As the first “Leg-Strong” number is 0, so, a 1 in input should correspond to 0 as output.
- Subtract 1 from k.
- Express k in base-5 representation.
- Multiply result from step-2 by 2.
- Output the result from step 3.
For Example:
Let k = 13
1. k=k-1; ---> (k=12)
2. Base-5 representation of 12 is 22.
3. Multiplying 22 by 2, we get, 44.
4. Output 44.
TIME COMPLEXITY:
O(log(k,base=5)) - Expressing k in base-5 number system.