ACL1 - Editorial

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.

  1. Subtract 1 from k.
  2. Express k in base-5 representation.
  3. Multiply result from step-2 by 2.
  4. 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.

//