You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

PROBLEM LINK:

Practice

Contest

DIFFICULTY:

EASY-MEDIUM

PRE-REQUISITES:

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)
You can read more about algorithm here
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

asked 26 Dec '14, 20:58

sainath_b's gravatar image

3★sainath_b
3842613
accept rate: 11%

edited 28 Dec '14, 14:19

admin's gravatar image

0★admin ♦♦
19.7k350498541


This solutions works but the space complexity would be high and will take a little more time the original editorial solution.

link

answered 26 Dec '14, 23:33

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2912319
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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