Suppose I have a simple equation of the form:
7x + 4y = n
where n is chosen by us and x, y and n are all positive integers. This is the only equation which is given to us. Among the possible solutions we need the solution (x,y) in which x is the smallest. e.g.
7x + 4y = 14, then (2, 0) is the solution
7x + 4y = 15, then (1, 2) is the solution
7x + 4y = 32, then (4, 1) and (0, 8) are the possible solutions,
of which (0, 8) is the correct solution
I would like to design an algorithm to calculate it in the least possible running time. The current algorithm which I have in mind goes something like this:
Given an input n
Calculate max(x) = n/7
for i = 0 to max(x)
If the equation 7*i + 4*y = n holds
return value of i and y
else
continue
This algorithm, I presume, can have a running time of upto O(n) in worst case behaviour. Is there some better algorithm to compute the solution?
If the equation 7*i + 4*y = n holds
i you get from the loop but what is y?