Solve equation with 3 variables

Question

I am prepping for an interview and I am trying to solve this question.

I want to know if I can find integers x, y, and z to satisfy the following equation without using any python modules.

4x + 6y + 11z = 31

I can come up with a solution that is O(n^3) by limiting the value of either x, y, or z by 31/coefficient. I am wondering if there is a more efficient way.

def isValid(denoms, target):
    maxX = target//denoms[0]
    maxY = target//denoms[1]
    maxZ = target//denoms[2]
    
    for x in range(maxX):
        for y in range(maxY):
            if ((x * denoms[0]) + (y * denoms[1]) > target):
                break
            
            z = target - (denoms[0] * x) - (denoms[1] * y)
            if int(z) == z:
                return True
    return False

print(isValid([4, 6, 8], 35))

Does this answer your question? [Is there a python module to solve linear equations?](https://stackoverflow.com/questions/6789927/is-there-a-python-module-to-solve-linear-equations) — sophros, Jan 11 '21 at 18:52
O(n^2): iterate over possible values for `x` and `y`. For any given value of `x` and `y`, there's only one possible value for `z`. So you can cut down on one order of magnitude in that way — inspectorG4dget, Jan 11 '21 at 18:54
this is one equasion with 3 variables, there is always solusion. — jonathan, Jan 11 '21 at 18:56
I mentioned this in the post but x, y, and z need to be integers. Also, I am looking for an algorithm so I would prefer not to use modules. I only need to find if a solution exists, not a list of solutions — Sri, Jan 11 '21 at 18:56
There are certain optimizations you can do. Since you are not considering negative integers. You can check conditions like `if (4x > 31): break` and `if (4x + 6y > 31): break` — Albin Paul, Jan 11 '21 at 18:57
This is a good example of a question that is a LOT easier if you think about how you solve it without programming. How do you solve it by hand? If you're familiar with linear algebra and matrices, there's a route for you. If not, you can think about conditionals for early stopping conditions. — Chrispresso, Jan 11 '21 at 19:02
@Sri can you give an example of equation in this format that would not return true ? — Richard D, Jan 11 '21 at 19:13
@AdamHughes: OP said *integers*. 31/11 is not an integer last I checked. — gspr, Jan 11 '21 at 19:16
@RichardD, I am updating my post now with my most up to date solution thanks to suggestions by inspectorG4dget and Albin Paull. A solution that would return false is denoms = [2, 4, 6], target = 11 — Sri, Jan 11 '21 at 19:17

jonathan · Answer 1 · 2021-01-12T13:44:30.967

1

I'm not sure this is the most efficient way but this solusion is O(n^2) .

def isValid(denoms, target):
    x = 0
    while x * denoms[0] <= target:
        y = 0
        while x * denoms[0] + y * denoms[1] <= target:
            if (target - (x * denoms[0] + y * denoms[1]) / denoms[2]).is_integer() :
                return True
            y += 1
        x += 1
    return False

EDIT: bugfix in the privios code

def isValid(denoms, target):
    x = 0
    while x * denoms[0] <= target:
        y = 0
        while x * denoms[0] + y * denoms[1] <= target:
            if ((target - (x * denoms[0] + y * denoms[1])) / denoms[2]).is_integer() :
                return True
            y += 1
        x += 1
    return False

edited Jan 12 '21 at 13:44

answered Jan 11 '21 at 19:14

jonathan

269
1
7

your function does not return the correct answer for the example, from OP's comment A solution that would return false is denoms = [2, 4, 6], target = 11 @jonathan – Richard D Jan 12 '21 at 00:35
It should return false for denoms [2, 4, 6],target =11. There is no solution for the equation with int numbers – jonathan Jan 12 '21 at 05:48
I know yours returns true – Richard D Jan 12 '21 at 11:25
ok, sory I didn't see that, fixed the bug – jonathan Jan 12 '21 at 13:45

Richard D · Answer 2 · 2021-01-12T00:54:38.417

Here is a completed function that I believe would give you the fastest results for this specific use case of xfactor * x + yfactor * y + zfactor * z = target and factor is not zero. this could be made to work for any function of the form:

Sum(nfactorn + ... + (n+1)Factor(n+1))

def isValid(factors,target):
     numbers = [ float(x) for x in factors]
   # numbers.sort()
    xFactor = numbers[0]
    yFactor = numbers[1]
    zFactor = numbers[2]
    print(xFactor)
    # total = xFactor + yFactor + zFactor
    # #find the min value if x = 0
    remainderMinX = target % (yFactor + zFactor)
    remainderCheckOnX = remainderMinX % xFactor
    
    # #find the min value if y=0
    remainderMinY = target % (xFactor + zFactor)
    remainderCheckOnY = remainderMinY % yFactor
    # #find the min value if z = 0
    remainderMinZ = target % (xFactor + yFactor)
    remainderCheckOnZ = target % (zFactor)
    
  
    
    # #find the min value if x>=1 y>=1 z>=1 and x =y =z
    # #special condition
    remainderMinMax = target % (xFactor + yFactor + zFactor)
    
    
   
    # #x=0, y=0, z=? remainderMinMax % xfactor = 0 is a true condition
    remainderMinXY = target % zFactor
    print(remainderMinXY)
    
    
    #  #x=0, y=?, z=0 remainderMinMax % yfactor = 0 is a true condition
    remainderMinXZ = target % yFactor
  
    
    #  #x=?, y=0, z=0 remainderMinMax % zfactor = 0 is a true condition
    remainderMinYZ = target % xFactor
   
    
    # #checks the conditions if x>1 and y = z 
    remainderMinMaxOfRemainderMinMaxX = remainderMinMax % xFactor
   
    
    # #checks the conditions if y>1 and x = z 
    remainderMinMaxOfRemainderMinMaxY = remainderMinMax % yFactor
 
    
    # #checks the conditions if z>1 and x = y 
    remainderMinMaxOfRemainderMinMaxZ = remainderMinMax % zFactor
  
    
    
    ## check the condition
    remainderMinMaxOfRemainderMinMaxXY = remainderMinMax % (xFactor +yFactor)
   
    
    remainderMinMaxOfRemainderMinMaxYZ = remainderMinMax % (yFactor + zFactor)
   
    
    remainderMinMaxOfRemainderMinMaxXZ = remainderMinMax % (xFactor + zFactor)
  
    
   
    if remainderMinY ==0 or remainderMinX ==0 or remainderMinZ ==0 or remainderCheckOnX ==0 or remainderCheckOnY==0 or remainderCheckOnZ ==0 or remainderMinMax ==0 or remainderMinXY==0 or remainderMinXZ ==0 or remainderMinYZ ==0 or remainderMinMaxOfRemainderMinMaxX ==0 or remainderMinMaxOfRemainderMinMaxY ==0 or remainderMinMaxOfRemainderMinMaxZ ==0 or remainderMinMaxOfRemainderMinMaxXY==0 or remainderMinMaxOfRemainderMinMaxYZ==0 or remainderMinMaxOfRemainderMinMaxXZ ==0 :
        return True
    
    else: 
        return False

This would also work if the equation was for example 5.5x + 4y + 6z = 31

Solve equation with 3 variables

2 Answers2