2
\$\begingroup\$

I've naively tried to gradually increase two values so eventually, they sum to a targeted value.

Since this code runs many times and eventually for very large values, I don't know how to optimize so that it doesn't take more than 0.5 seconds.

def coefTargetSum(R, X, Y):
    coefResult = []
    for x in range(R):
        for y in range(R):
            if x * X + y * Y == R:
                coefResult.extend([x, y])
                return coefResult
    return -1
\$\endgroup\$
1
\$\begingroup\$
  • Rearrange the equation to find one variable from another.

    \$R = xX + yY\$
    \$xX = R - yY\$
    \$x = \frac{R - yY}{X}\$

    And so, if you don't want negative values of \$x\$, then you need to limit the range to \$\lfloor \frac{R}{X} \rfloor + 1\$.

    This also will return floats, which for the most part shouldn't make a difference as it's a subtype of int. However as we're limiting the results to integers then converting the number to an int could make sense.

  • I also wouldn't return -1, but would instead use None or an empty list. This is as -1 makes no logical sense.

  • And rather than extending a list with another list, just return the wanted list. Better you could return a tuple.

This allows for:

def coefTargetSum(R, X, Y):
    for y in range(R // X + 1):
        x = (R - y*Y) / X
        if x % 1 == 0:
            return int(x), y
    return None
\$\endgroup\$
7
  • \$\begingroup\$ I'm confused, to me that looks like a test for an even number after an integer division in python2. \$\endgroup\$
    – stefan
    Nov 22 '17 at 20:37
  • \$\begingroup\$ @stefan you're correct, I messed up the operator, it should have been a %, rather than a &. I also assume Python 3, or from __future__ import division. \$\endgroup\$
    – Peilonrayz
    Nov 23 '17 at 0:35
  • \$\begingroup\$ Still you are returning float which may result in a TypeError.And you return negative x values as your loop runs up to R for no reason and you do not test for it (coefTargetSum(24, 5, 11)). \$\endgroup\$
    – stefan
    Nov 23 '17 at 8:33
  • \$\begingroup\$ @stefan My code is purely for showing an alternate way to do something. It's rare to get a TypeError, but is adding int(...) that hard? So, the question doesn't say anything about results not being allowed to be negative. \$\endgroup\$
    – Peilonrayz
    Nov 23 '17 at 9:05
  • \$\begingroup\$ If the task was not without negative numbers the search space would be infinite. You do limit the seach space to range(R), so you are accepting the non-negative-constraint. Just not fully. \$\endgroup\$
    – stefan
    Nov 23 '17 at 9:11
0
\$\begingroup\$

There is some information missing. From your code I assume you work with integers.

  • there is no need to iterate the whole range up to R
  • you may test the second variable in a closed form

If indeed you want a single result only

def coefTargetSum(R, X, Y):
    for x in range(R // X + 1):
        y = (R - x*X) / Y
        if y.is_integer():
            return [x, int(y)]
    return None

however if you want a list of all results

def coefTargetSum(R, X, Y):
    coefResult = []
    for x in range(R // X + 1):
        y = (R - x*X) / Y
        if y.is_integer():
            coefResult.append((x, int(y)))
    return coefResult

In your case the testing of the second variable is quite cheap, it is a division only. however there are many cases where testing in a closed form is not possible (modulo operations, ...) or expensive (sqrt, ...). Then you have to try all combinations. But again you can do this more effective by avoiding to test previously known impossible combinations. you fill the sum completely with one type of elements (X) and depending on whether it is to big or not you continue by removing an X or adding a Y.

def coefTargetSum(R, X, Y):
    x = R // X
    y = 0
    coefResult = []
    while x >= 0:
        sum = x * X + y * Y
        if sum == R:
            coefResult.append((x, y))
        if sum >= R:
            x -= 1
        else:
            y += 1
    return coefResult
\$\endgroup\$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .