Project Euler 5: Smallest Multiple - Project Euler Detailed Solutions

Problem

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution Approach

In this problem of smallest multiple, we have to find the smallest possible number which divides every number between 1 to 20. The smallest possible number which divides a set of numbers is called LCM (Lowest Common Multiple). So essentially we have to find LCM of numbers between 1 to 20.

There is no direct formula to calculate LCM other than looking at the factors. Although, there are two essential formulas related to LCM which we can use to our advantage. First one is LCM(x,y) * GCD(x, y) = x * y where x and y are numbers. The second important formula which will help us is LCM(x, y, z) = LCM (x,LCM(y,z)) where again x,y and z are numbers.

We can find the GCD of a number easily by the Euclidean algorithm. This way we can find the LCM by substituting it in the first formula. The second formula can be used to accumulate the LCM from 1 to 20.

Time and Space Complexities

The time complexity of this approach is O(nk) where n is 20 and k is the time to calculate GCD. So ultimately the time complexity is O(n). The space complexity of this approach is O(1) as we are using one variable to store the lcm.

Coding Approach

Coming to the code part of the approach we first initialize the variable which will store our final answer. Let us call this finalLcm. Then we iterate through 1 to 20 and find the LCM using the two formulas discussed above. To calculate the LCM and GCD we can create individual methods to obtain modularity. We store the intermediate LCM in the variable defined above. In the end, we just have to return that as the answer.

We can also make the work easier in this particular case by iterating through 11-20 only. We are already given LCM of the first 10 numbers.

Solution Code

Java Solution

def GCD(x,y):
    if y==0: return x
    return GCD(y, x%y)

def LCM(x, y):
    return (x*y)//GCD(x,y)

def computeLCM():
	finalLCM = 1
	for i in range(1, 21):
		finalLCM = LCM(finalLCM, i)
	return finalLCM


if __name__ == "__main__":
	print(computeLCM())

def GCD(x,y):

if y==0: return x

return GCD(y, x%y)

def LCM(x, y):

return (x*y)//GCD(x,y)

def computeLCM():

finalLCM = 1

for i in range(1, 21):

finalLCM = LCM(finalLCM, i)

return finalLCM

if __name__ == "__main__":

print(computeLCM())

Python Solution

def largest_palindrome_product():
	result = max(i * j
		for i in range(100, 1000)
		for j in range(100, 1000)
		if str(i * j) == str(i * j)[ : : -1])
	return str(result)
	
print(largest_palindrome_product)

def largest_palindrome_product():

result = max(i * j

for i in range(100, 1000)

for j in range(100, 1000)

if str(i * j) == str(i * j)[ : : -1])

return str(result)

print(largest_palindrome_product)

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding 🙂