CODEWITHSUNDEEP
python
Sri
Sri

Reputation: 2328

Solve equation with 3 variables

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))

Upvotes: 2

Views: 294

Answers (2)

jonathan
jonathan

Reputation: 269

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

Upvotes: 1

Richard D
Richard D

Reputation: 142

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

Upvotes: 0

Related Questions