Dig Deeper
Nested for loop
Nested For Loop
def largest(min_factor, max_factor):
if min_factor > max_factor:
raise ValueError("min must be <= max")
result = 0
answer = []
for number_a in range(min_factor, max_factor+1):
for number_b in range(min_factor, max_factor+1):
if number_a * number_b >= result:
test_value = str(number_a * number_b)
if test_value == test_value[::-1]:
if number_a * number_b > result:
answer = []
result = int(test_value)
answer.append([number_a, number_b])
if result == 0:
result = None
return (result, answer)
def smallest(min_factor, max_factor):
if min_factor > max_factor:
raise ValueError("min must be <= max")
result = 0
answer = []
for number_a in range(min_factor, max_factor+1):
for number_b in range(min_factor, max_factor+1):
if number_a * number_b <= result or result == 0:
test_value = str(number_a * number_b)
if test_value == test_value[::-1]:
if number_a * number_b < result:
answer = []
result = int(test_value)
answer.append([number_a, number_b])
if result == 0:
result = None
return (result, answer)
The largest and smallest functions are very similar here.
Although there are some small differences.
The largest function starts with checking if the min_factor is bigger than the max_factor.
If it is, it raises a ValueError.
After that, it initializes the result to 0 and the answer to an empty list.
Then it starts a for in range loop.
The outer for loop iterates over the range of numbers from min_factor to max_factor.
The inner for loop iterates over the same range of numbers.
Then it checks if the product of the two numbers is bigger than the result.
If it is, it converts the product to a string and checks if it is a palindrome.
We can check if a string is a palindrome by comparing it to its reverse.
There are multiple ways to reverse a string.
The most common way is to use slice notation.
The slice notation is string[start:stop:step].
You can read more about it in: reverse string with slice.
If the string is a palindrome, the solution next checks if the product is bigger than the current result.
If the product is bigger, the answer list is cleared, and the current result is set to the most recent product.
Then it appends the two numbers to the answer list.
After the two for loops, it checks if the result is 0.
If it is, it sets the result to None.
Then it returns the result and the answer.
The smallest one is very similar.
The differences are that it checks if the product is smaller than the result or if the result is 0.
And that it reset result outside of the if statement.
Instead of inside of it.
Nested for loop optimized
Nested For Loop Optimized
This approach shows that just a few changes can improve the running time of the solution significantly.
def largest(min_factor, max_factor):
if min_factor > max_factor:
raise ValueError("min must be <= max")
result = 0
answer = []
for number_a in range(max_factor, min_factor - 1,-1):
was_bigger = False
for number_b in range(max_factor, number_a - 1, -1):
if number_a * number_b >= result:
was_bigger = True
test_value = str(number_a * number_b)
if test_value == test_value[::-1]:
if number_a * number_b > result:
answer = []
result = int(test_value)
answer.append([number_a, number_b])
if not was_bigger:
break
if result == 0:
result = None
return (result, answer)
def smallest(min_factor, max_factor):
if min_factor > max_factor:
raise ValueError("min must be <= max")
result = 0
answer = []
for number_a in range(min_factor, max_factor+1):
was_smaller = False
for number_b in range(min_factor, max_factor+1):
if number_a * number_b <= result or result == 0:
was_smaller = True
test_value = str(number_a * number_b)
if test_value == test_value[::-1]:
if number_a * number_b < result:
answer = []
result = int(test_value)
answer.append([number_a, number_b])
if not was_smaller:
break
if result == 0:
result = None
return (result, answer)
This approach is very similar to the nested for loop approach, but it has a few optimizations.
To optimize the largest function, we have to start the inner loop from the maximum factor and proceed down to the minimum factor.
This allows us to stop the inner loop earlier than before.
We also set the minimum value in the inner loop to the current value of the outer loop.
Here is an example of how the algorithm works and why the loops need to be modified.
Say we take maximum to be 99 and the minimum 10.
In the first round:
x = [99 , 98, 97 ...]
y = [99]
And already we have our result: 9009[91,99]
Although the loops have to continue to make us sure there are no higher values.
x = [98, 97, 96 ...]
y = [99, 98]
...
x = [90, 89, 88 ...]
y = [99, 98,97,96,95,94,93,92,91,90]
Here we can see that the highest value for this “run” is 90 * 99 = 8910.
Meaning that running beyond this point won’t give us any values higher than 9009.
That is why we introduce the was_bigger variable.
With was_bigger, we can check if the inner loop has a bigger value than the current result.
If there has not been a bigger value, we can stop the inner loop and stop the outer loop.
We do that by using the break statement.
If we hadn’t modified the direction of the inner loop, it would have started from the minimum factor and gone up to the maximum factor.
This would mean that for every new run in the outer loop, the values would be bigger than the previous run.
The smallest function is optimized in a similar way as largest function compared to the original approach.
The only difference is that we have to start the inner loop and outer loop from the minimum factor and go up to the maximum factor.
Since what we want is the smallest value, we have to start from the smallest value and go up to the biggest value.
Source: Exercism python/palindrome-products