Given A, B and N. Find x and y that satisfies equation Ax + By = N. If there's no solution print -1 in place of both x and y. 
Note: There are Multiple solutions possible. Find the solution where x is minimum. x and y should both be non-negative.
 
Example 1:
Input:
A = 2, B = 3, N = 7
Output:
2 1
Explanation:
2*2 + 3*1 = 7.
Example 2:
Input:
A = 4, B = 2, N = 7
Output:
-1 -1
Explanation:
There's no solution for x and y the equation.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function findXandY() which takes 3 Integers A,B and N as input and returns a list of 2 integers with the first integer x and the second being y.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= A,B <= 10^{5}
0 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def findXandY(self, A , B , N):

        # code here

Solutions:
class Solution:

	def findXandY(self, A, B, N):
		if N % B == 0:
			return [0, N // B]
		for i in range(1, N):
			c = N - A * i
			if c > 0 and c % B == 0:
				return [i, c // B]
		return [-1, -1]


import math

class Solution:

	def findXandY(self, a, b, n):
		x = -1
		y = -1
		for i in range(n // a + 1):
			for j in range(n // b + 1):
				if n == a * i + b * j:
					return (i, j)
		return (x, y)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(A, B, N) = map(int, input().split())
		ob = Solution()
		ptr = ob.findXandY(A, B, N)
		print(*ptr)


class Solution:

	def findXandY(self, A, B, N):
		for i in range(N // A + 1):
			if (N - A * i) % B == 0:
				x = i
				y = (N - A * i) // B
				return [x, y]
		return [-1, -1]


class Solution:

	def findXandY(self, a, b, c):
		if c == 0:
			return [0, 0]
		for i in range(c):
			z = (c - a * i) / b
			if z < 0:
				return [-1, -1]
			if z == int(z):
				return [i, int(z)]
		return [-1, -1]