wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> perfect squares in a sorted aaray
        
(Message started by: srikanth.iiita on Mar 31^st, 2010, 8:23am)

Title: perfect squares in a sorted aaray
Post by srikanth.iiita on Mar 31^st, 2010, 8:23am

given an sorted array ...
find all numbers which are perfect squares...
propose the best possible method

Title: Re: perfect squares in a sorted aaray
Post by SMQ on Mar 31^st, 2010, 8:27am

[hide]Pretend you have a second sorted list containing only perfect squares and use the standard algorithm for finding the common elements of the two lists. Rather than actually maintaining a pointer into the pretend list, merely increment an integer when you would advance the pointer.
[/hide]

--SMQ

Title: Re: perfect squares in a sorted aaray
Post by srikanth.iiita on Mar 31^st, 2010, 8:36am

constant memory solution plz...
can we take the help of binary search .. here

Title: Re: perfect squares in a sorted aaray
Post by SMQ on Mar 31^st, 2010, 8:43am

The solution above is constant memory, and O(n + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifMAX(A)) time which is approximately O(n) unless A is very sparse.

--SMQ

Title: Re: perfect squares in a sorted aaray
Post by Grimbal on Mar 31^st, 2010, 8:48am

That IS constant memory.

You just pretend to have a second array with squares. Actually the values are computed on the fly.

(This goes against what I heard, that when you start pretending things, you better have a good memory).

PS: as SMQ explained faster than me.

Title: Re: perfect squares in a sorted aaray
Post by spicy on Apr 7^th, 2010, 8:39am

Will it still be a good approach if elements have huge variations?
like
2,4444,2309129 etc

Title: Re: perfect squares in a sorted aaray
Post by towr on Apr 7^th, 2010, 9:05am

You can use floor(sqrt(N))²==n to check squareness.

Title: Re: perfect squares in a sorted aaray
Post by william wu on Apr 7^th, 2010, 4:53pm

on 04/07/10 at 09:05:09, towr wrote:

You can use floor(sqrt(N))²==n to check squareness.

Seems like this would be a better approach if we have huge variations, since otherwise we'd be incrementing the pretend array for a long time.

In[1]:= (Floor[Sqrt[#]^2 == #) & /@ {3, 13, 64, 15, 36, 19}
Out[1]= {False, False, True, False, True, False}

However, this approach also requires floating point arithmetic, to take the square root -- whereas SMQ's solution does not.

I read about an integer-based square root test here:
http://www.advogato.org/person/fxn/diary.html?start=465

Title: Re: perfect squares in a sorted aaray
Post by towr on Apr 8^th, 2010, 12:45am

You can also do binary search for the next square smaller or equal to the next candidate in the array.

Title: Re: perfect squares in a sorted aaray
Post by TenaliRaman on Apr 10^th, 2010, 8:08am

You can have an increment lookup table. Look at the current square value of the pretend array and the next y value in the give array. If the difference is greater than some N, choose an appropriate increment value.

You can even have a function that computes the best possible increment.

y0 = x0^2
y1 = (x0 + Dx)^2
Dy = 2 * x0 * Dx + Dx^2
Dx = (- 2 * x0 +/- sqrt(4 * x0^2 + 4 * Dy)) / 2
x0 + Dx = sqrt(x0^2 + Dy)

One just needs an integer root here, which can computed without resorting to floating point arithmetic.

However, having the lookup tables might be faster than the above.

on 04/07/10 at 16:53:36, william wu wrote:

Seems like this would be a better approach if we have huge variations, since otherwise we'd be incrementing the pretend array for a long time. <snip>