How to solve Project Euler 99
Problem statement
Let the five lines below be the content of a text file.
5,2
6,9
4,10
10,2
5,3
These are base-exponent pairs, separated by a comma. We have to find which line will have maximum value after the execution of the mathematical expression, that is, base^exponent.
The first line evaluates to 5^2, that is, 25. The second line gives 6^9, that is, 10077696. Similarly, the third line gives 1048576, the fourth line gives 100, and the fifth line gives 125.
Out of these five base-exponent pairs, the pair on the second line evaluates to the maximum value, 10077696. Hence, the answer is line two.
Now, we have to find out which line evaluates to the maximum value amongst 1000 lines.
The largest exponential
The text file given below contains one thousand lines with a base-exponent pair on each line. We have to determine which line number has the greatest numerical value.
Solution approach
The hurdles in solving this problem with brute force are that both the base and exponent are quite large numbers, and the power operation itself is a time-consuming task.
However, for this problem, we don’t have to calculate each value, we just need to compare them.
Alternative way of comparing two base-exponent pairs.
first pair = (a,b)
firstValue = a^b
second pair = (c,d)
secondValue = c^d
According to the power property of logarithms, log(x^y) = y*log(x).
If firstValue>secondValue,
and we take log on both sides then.
=> log(firstValue) > log(secondValue).
=> log(a^b) > log(c^d)
=> b* log(a) > d* log( c)
We’ll replace the base^exponent operation with exponent*log(base). This change will largely reduce execution time as the second operation is essentially only the multiplication of two quantities.
Note: Paste the contents of the text file given above in the input box to run the code.
from math import log
with open('__ed_input.txt','r') as FILE:
cnt=1
maxValue=0
maxIndex=0
while (cnt<=1000):
base,exponent = list(map(int,FILE.readline().split(',')))
value = exponent*log(base)
if maxValue<value:
maxValue = value
maxIndex = cnt
cnt+=1
print(maxIndex)Enter the input below to be saved in file __ed_input.txt
Code explanation
-
In line 1, we import the log function from the math library.
-
In line 3, we open a file named “__ed_input.txt” as
FILE. This file contains the input text. -
In lines 4-6,
cntis the variable which represents the line numbers and is used to traverse through the data.maxValueis the variable that stores the maximum value of the base-exponent pair. AndmaxIndexstores the line number, where themaxValueoccurs. -
In lines 8-16, we We start the while loop till the
cnt<=1000.-
In line 9, we take the (base, exponent) pair as input from
FILE. -
In line 12-14, we update the values of
maxValueandmaxIndex. IfmaxValue< value. -
In line 16, we increment the line number, that is,
cnt.
-
-
In line 19, as
maxIndexcontains the line number of wheremaxValueoccurred, we printmaxIndex.
RELATED TAGS
CONTRIBUTOR
View all Courses
