CODEWITHSUNDEEP
c++pythoncalgorithmmath
user2256798
user2256798

Reputation:

Finding solution set of a Linear equation?

I need to find all possible solutions for this equation:

x+2y = N, x<100000 and y<100000.

given N=10, say.

I'm doing it like this in python:

for x in range(1,100000):
    for y in range(1,100000):
        if x + 2*y == 10:
             print x, y

How should I optimize this for speed? What should I do?

Essentially this is a Language-Agnostic question. A C/C++ answer would also help.

Upvotes: 1

Views: 849

Answers (5)

Lefteris E
Lefteris E

Reputation: 2814

we can iterate over the domain of y and calculate x. Also taking into account that x also has a limited range, we further limit the domain of y as [1, N/2] (as anything over N/2 for y will give negative value for x)

x=N;
for y in range(1,N/2-1):
     x = x-2
     print x, y
  • This just loops N/2 times (instead of 50000)
  • It doesn't even do those expensive multiplications and divisions

Upvotes: 3

user2032663
user2032663

Reputation:

Lefteris E 's answer is the way to go,

but I do feel y should be in the range [1,N/2] instead of [1,2*N]

Explanation:

x+2*y = N

//replace x with N-2*y
N-2*(y) + 2*y = N
N-2*(N/2) + 2*y = N
2*y = N

//therefore, when x=0, y is maximum, and y = N/2
y = N/2

So now you can do:

for y in range(1,int(N/2)):
   x = N - (y<<1)
   print x, y

Upvotes: 0

gefei
gefei

Reputation: 19816

if x+2y = N, then y = (N-x)/2 (supposing N-x is even). You don't need to iterate all over range(1,100000)

like this (for a given N)

if (N % 2): x0 = 1
else: x0 = 0
for x in range(x0, min(x,100000), 2):
    print x, (N-x)/2

EDIT: you have to take care that N-x does not turn negative. That's what min is supposed to do

The answer of Leftris is actually better than mine because these special cases are taken care of in an elegant way

Upvotes: 5

taocp
taocp

Reputation: 23644

You may try to only examine even numbers for x given N =10; the reason is that: 2y must be even, therefore, x must be even. This should reduce the total running time to half of examining all x.

If you also require that the answer is natural number, so negative numbers are ruled out. you can then only need to examine numbers that are even between [0,10] for x, since both x and 2y must be not larger than 10 alone.

Upvotes: 0

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272627

This runs in quadratic time. You can reduce it to linear time by rearranging your equation to the form y = .... This allows you to loop over x only, calculate y, and check whether it's an integer.

Upvotes: 1

Related Questions