×

# KGP14J Editorial (Different Approach)

This problem already has an Editorial. You can look at Here
http://discuss.codechef.com/questions/59789/kgp14j-editorial

But I have a completely different idea with basic mathematics. Thats why iam writing a new Editorial.

EASY-MEDIUM

Maths

# PROBLEM:

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

# EXPLANATION:

There exists a very nice algorithm to multiply a very large number (stored in array) and a small number(that lies in integer range)
http://www.codechef.com/wiki/tutorial-small-factorials

Here is the pseudo code:
a[]//used to store x^e
b[]//used to store y
mx=0// used to store number of digits in x
my=0// used to store number of digits in y
//storing y in b[]..
while(y>0){
b[my++]=y%10;
y/=10;
}
// storing y complete
//storing x^0=1 intially
mx=1
a[0]=1
exp=0
while(true){
multiply x stored in array with x using above algorithm;
exp++;
//now a contains x^exp
if(y is prefix of x^exp)
ans=exp and break;

}
print ans

Here is my C++ code :
http://www.codechef.com/viewsolution/5651534

3842613
accept rate: 11%

19.7k350498541

 0 This solutions works but the space complexity would be high and will take a little more time the original editorial solution. answered 26 Dec '14, 23:33 291●2●3●19 accept rate: 10%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,648
×1,175

question asked: 26 Dec '14, 20:58

question was seen: 1,031 times

last updated: 28 Dec '14, 14:19