I have an O(1) way to find the answer.

just put all the numbers in a array of boolean.

var

n,i,caint:longint;

b:array[-100000..100000]of boolean;

begin

readln(n);

fillchar(b,sizeof(b),false);

for i := 1 to n do

begin

readln(caint);

b[caint]:=true;

end;

readln(n);

for i := 1 to n do

begin

readln(caint);

if b[10000-caint] then

begin

writeln('YES');

halt;

end;

end;

writeln('NO');

end.

*Edited by author 10.09.2009 08:34*

Re: I have an O(1) way to find the answer.

I think it is O(n2)

Re: I have an O(1) way to find the answer.

It is O(n), not O(1)

And there's another O(n) solution for this problem, which requires only O(n) memory instead of O(v) in your case, where v is max value of a_i.

Re: I have an O(1) way to find the answer.

Yes , SkidanovAlex right. O(n).

Re: I have an O(1) way to find the answer.

Posted by

Mariana 24 Sep 2012 16:31

thanks