question
A mathematician purchases four items from a convenience store. He notices that the sum and product of the prices of the four items comes out to $7.11. Write a function to determine the prices of the four items.
A brute force program for this question would take too long. However we can make it much more efficient by considering the divisors of our required product.
We'll first start by putting down two equations. Note that below the variables are in cents.
a + b + c + d = 711
(a/100) * (b/100) * (c/100) * (d/100) = 7.11
Or more simply: a * b * c * d = 711,000,000 = 7.11 * 108
Instead of attempting a naive brute force method (which would require 7114 ~ 255 Billion calculations), we can make our brute force attempt much more efficient by some simple realizations. We know that the theoretical maximum the variables can be is 711 and that they must be a proper divisor of 7.11 * 108. And so when implementing code, first find the divisors from 1 through 711. This narrows our choices down significantly in our brute force attempt.
Another tidbit of information that we can obtain is that 79 is a prime factor of 7.11 * 108. This comes in handy because we know that one of the variable has to be a multiple of 79 (with a maximum of 9 because 9 * 79 = 711). Using nested loops iterating through the possible factors, we can set the final loop to iterate only through the possible multiples of 79. This will further reduce the number of computations required.
Implementing and running the above brute force solution should give you the prices of the items: $1.20, $1.25, $1.50, $3.16
Thoughts or alternate solution? Let us know in the comments below!
a + b + c + d = 711
(a/100) * (b/100) * (c/100) * (d/100) = 7.11
Or more simply: a * b * c * d = 711,000,000 = 7.11 * 108
Instead of attempting a naive brute force method (which would require 7114 ~ 255 Billion calculations), we can make our brute force attempt much more efficient by some simple realizations. We know that the theoretical maximum the variables can be is 711 and that they must be a proper divisor of 7.11 * 108. And so when implementing code, first find the divisors from 1 through 711. This narrows our choices down significantly in our brute force attempt.
Another tidbit of information that we can obtain is that 79 is a prime factor of 7.11 * 108. This comes in handy because we know that one of the variable has to be a multiple of 79 (with a maximum of 9 because 9 * 79 = 711). Using nested loops iterating through the possible factors, we can set the final loop to iterate only through the possible multiples of 79. This will further reduce the number of computations required.
Implementing and running the above brute force solution should give you the prices of the items: $1.20, $1.25, $1.50, $3.16
Thoughts or alternate solution? Let us know in the comments below!