Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

Posted by

tau 26 Jun 2001 21:04

Could someone help me. I've tried to solve the problem

using a classical Lee approach and for the worst case

when the numbers are very small (eg. 1 or 2), the program

takes about 4 secs on my PII-350.

The Dirichlet method of solving isn't a better solution

because it has the same complexity.

Could someone give me a hint on optimizing my algorithm or

if you got a better solution could you please forward it.

Thankz.

Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

In this problem you need to note 2 things:

1) There is always solution.

2) The solution is always a continuous sequence.

Yes, O(N) .

> Could someone help me. I've tried to solve the problem

> using a classical Lee approach and for the worst case

> when the numbers are very small (eg. 1 or 2), the program

> takes about 4 secs on my PII-350.

>

> The Dirichlet method of solving isn't a better solution

> because it has the same complexity.

>

> Could someone give me a hint on optimizing my algorithm

or

> if you got a better solution could you please forward it.

>

> Thankz.

Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

Posted by

tau 28 Jun 2001 15:07

> In this problem you need to note 2 things:

> 1) There is always solution.

> 2) The solution is always a continuous sequence.

Thanks you.

Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

> > In this problem you need to note 2 things:

> > 1) There is always solution.

> > 2) The solution is always a continuous sequence.

>

> Thanks you.

I can't understand 2) The solution is always a continuous sequence.

What means continuous sequence?

ex) 1. 4 5 6 7 8 9

or

2. Input[4], Input[5], Input[6], Input[7], Input[8],

Input[9]?

I don't know..

Give me more hints...

It's the choice 2

Posted by

meoden 28 Feb 2002 11:47

> ex) 1. 4 5 6 7 8 9

> or

> 2. Input[4], Input[5], Input[6], Input[7], Input[8],

> Input[9]?

It's the second one.

S[i]= (input[1]+input[2]+..+input[i]) mod n;

If you can find i such as s[i]=0; it's ok.

If not, you always find i, j: s[i]=s[j];

The sol is input[i+1]...input[j]. OK?

Re: It's the choice 2

Why the answer is such a sequence of input?

Is it impossible that : input[1],input[7],input[9].......

Thanks.

> It's the second one.

> S[i]= (input[1]+input[2]+..+input[i]) mod n;

> If you can find i such as s[i]=0; it's ok.

> If not, you always find i, j: s[i]=s[j];

> The sol is input[i+1]...input[j]. OK?

>

>

Thank you!

I got AC.

Your explanation is perfect!

I think, I would have never invented anything better than O(n^2) myself.

Thanks once again!

rafailka.

Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

Posted by

Macarie 11 Apr 2005 15:04

O(N) -> compute partial sums then find two with same remainder modulo N and subtract them

Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

i think you're proffessor becasuse you find algorithm that every one know..

Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

i think you're proffessor becasuse you find algorithm that every one know..

Talking like you know everything

*Edited by author 28.05.2006 01:02*Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

what do you say

Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

4s on p2-350 is enough for oj

Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?

Posted by

zylm 7 Oct 2014 16:54

why it's always a continuous sequence?

*Edited by author 07.10.2014 17:00*