Author |
Topic: perfect squares in a sorted aaray (Read 1239 times) |
|
srikanth.iiita
Newbie
Posts: 33
|
 |
perfect squares in a sorted aaray
« on: Mar 31st, 2010, 8:23am » |
 Quote  Modify
|
given an sorted array ...
find all numbers which are perfect squares...
propose the best possible method
|
| « Last Edit: Mar 31st, 2010, 8:29am by srikanth.iiita » |
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: perfect squares in a sorted aaray
« Reply #1 on: Mar 31st, 2010, 8:27am » |
Quote Modify
|
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.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: perfect squares in a sorted aaray
« Reply #2 on: Mar 31st, 2010, 8:36am » |
Quote Modify
|
constant memory solution plz...
can we take the help of binary search .. here
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: perfect squares in a sorted aaray
« Reply #3 on: Mar 31st, 2010, 8:43am » |
Quote Modify
|
The solution above is constant memory, and O(n +  MAX(A)) time which is approximately O(n) unless A is very sparse.
--SMQ
|
| « Last Edit: Mar 31st, 2010, 8:44am by SMQ » |
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: perfect squares in a sorted aaray
« Reply #4 on: Mar 31st, 2010, 8:48am » |
Quote Modify
|
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.
|
| « Last Edit: Mar 31st, 2010, 8:49am by Grimbal » |
IP Logged |
|
|
|
spicy
Newbie
Gender: 
Posts: 8
|
|
Re: perfect squares in a sorted aaray
« Reply #5 on: Apr 7th, 2010, 8:39am » |
Quote Modify
|
Will it still be a good approach if elements have huge variations?
like
2,4444,2309129 etc
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: perfect squares in a sorted aaray
« Reply #6 on: Apr 7th, 2010, 9:05am » |
Quote Modify
|
You can use floor(sqrt(N))2==n to check squareness.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: perfect squares in a sorted aaray
« Reply #7 on: Apr 7th, 2010, 4:53pm » |
Quote Modify
|
on Apr 7th, 2010, 9:05am, towr wrote:| You can use floor(sqrt(N))2==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
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: perfect squares in a sorted aaray
« Reply #8 on: Apr 8th, 2010, 12:45am » |
Quote Modify
|
You can also do binary search for the next square smaller or equal to the next candidate in the array.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: perfect squares in a sorted aaray
« Reply #9 on: Apr 10th, 2010, 8:08am » |
Quote Modify
|
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 Apr 7th, 2010, 4:53pm, 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>
|
|
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print