KGP14J - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Lalit Kundu

DIFFICULTY:

EASY-MEDIUM

PRE-REQUISITES:

Maths

PROBLEM:

Given X and Y, find smallest E such that Y occurs as a prefix of XE. For example, Y ∈ {6,65,656,6561} are prefix of 38.

EXPLANATION:

We will iterate over E and if we naively do the power for each E, complexity will be higher. So, we need to quickly find the first K(<10) digits of XE, given X and E.

We write,
log10{XE} = E log10{X}.
Let’s say E log10{X} = 10*a + b ie. b is the decimal part in it.
Therefore, XE = 1010*a + b. Not that 10*a part contributes zeroes only, so we need only fractional part.
So, if we need first K digits of XE, we do 10b * 10K-1.

For example, we need to find first 5 digits of X=20132013.
X = 106650.637518850862 = 106650 * 100.637518850862.
Note that 106650 only contributes zeroes to X and not actuall digits.
So, first 5 digits will be integer part of 100.637518850862 * 104 = 43402.

SOLUTIONS:

Editorialist’s solution

1 Like