# Find 2 numbers that multiply to a number and add to another number

Here is my code, however, I am unsure whether it is the fastest way to achieve this objective.

import random

multiply_to = int(input("2 numbers must multiyply to: "))
solved = False

while solved == False:
nums = random.sample(range(-100, 150), 2)
if (nums[0] + nums[1] == add_to) and (nums[0] * nums[1] == multiply_to):
print(nums)
print('Solved')
break


Question: 1. Is it possible for the range to be set based upon the input of numbers given by the user.

• Using random numbers is one of the slowest ways to find the two numbers. The much faster way is to solve two equations, x1+x2=sum;x1x2=product, which is not hard. May 15 '20 at 7:27

# Code Review

while solved == False: is an awkward way of writing the loop condition. while not solved: would be clearer and more Pythonic.

You never set solved = True anywhere. Instead, you unconditionally break out of the loop. This means your loop could actually be written while True:, but I don't think this is clearer. Using solved = True instead of break would terminate the loop in an expected way.

This is verbose:

    nums = random.sample(range(-100, 150), 2)
if (nums[0] + nums[1] == add_to) and (nums[0] * nums[1] == multiply_to):


You could unpack nums into to individual variables, and avoid the [0] and [1] indexing operations, for more performant code:

    x1, x2 = random.sample(range(-100, 150), 2)
if x1 + x2 == add_to and x1 * x2 == multiply_to:


If you give values which can never work with integers, like add to 2 and multiply to 3, you have an infinite loop. You should have a "give up after so many attempts" procedure.

# Monte Carlo

As pointed out by Peilonrayz, there is an $$\O(1)\$$ solution to the problem.

However, if your goal is to utilize a Monte Carlo simulation method ...

If multiply_to is:

• positive, then the numbers must be the same sign, both positive or both negative, which you could determine by looking at the add_to sign,
• negative, then one number must be greater than zero, and the other must be less than zero,
• zero, then one number must be zero.

eg)

if multiply_to > 0:
else:
r1 = range(add_to + 1, 0)
r2 = range(add_to + 1, 0)

elif multiply_to < 0:
r1 = range(1, 150)   # A positive value in your initial range bracket
r2 = range(-100, 0)  # A negative value in your initial range bracket

else:
r2 = range(0, 1)

for _ in range(10_000):
x1 = random.choice(r1)
x2 = random.choice(r2)
if x1 + x2 == add_to and x1 * x2 == multiply_to:
print(f"Solved: {x1} + {x2} = {add_to}, {x1} * {x2} = {multiply_to}")
break
else:
print("Couldn't find a solution")

• Nice answer. I'd prefer while True over a flag. But otherwise agree +1. May 15 '20 at 19:59

Rather than generating two random numbers it would be much faster to generate one and determine the other.

\begin{align} x + y &= \text{sum}\\ x * y &= \text{product} \end{align}

Since $$\\text{sum}\$$ and $$\\text{product}\$$ are constants we can determine $$\y\$$ from either. And go on to find the equation that $$\x\$$ must hold.

\begin{align} x + y &= \text{sum}\\ y &= \text{sum} - x\\ x * y &= \text{product}\\ x * (\text{sum} - x) &= \text{product}\\ \text{sum}x - x^2 &= \text{product}\\ \end{align}

This means that we can find the solution by only using $$\x\$$, and determining $$\y\$$ after the fact.

We can see how this effects your code by using range rather than random.sample. When generating both $$\x\$$ and $$\y\$$ you'll need two for _ in range(n) loops, which are nested. This means your code will run in $$\O(n^2)\$$ time. With only $$\x\$$ it will however run in $$\O(n)\$$ time as it will have only one for loop.

However we can get better than $$\O(n)\$$ time. As you should be able to see that the math is producing a quadratic, and so we can just use the Quadratic Formula.

\begin{align} \text{sum}x - x^2 &= \text{product}\\ 0 &= x^2 - \text{sum}x + \text{product}\\ x &= \frac{\text{sum} \pm \sqrt{\text{sum}^2 - 4\text{product}}}{2}\\ y &= \text{sum} - x \end{align}

• You goofed your quadratic formula substitution. "-sum x" means "b = -sum", so the first term "-b" becomes "-(-sum)", which is "+sum", not "-sum". May 17 '20 at 15:06
• @AJNeufeld Indeed I must have misread something without a minus. Thank you :) May 17 '20 at 15:09