@Anshu
looks interesting. A few things -
>> To check the particular number square can be written as sum of two
squares or not. If it has any prime factor x such that x % 4 == 1 then only.
- What would be the complexity of finding prime factors. Did you factor
in it in overall complexity.
- "if it has any prime factor x such that x % 4 == 1 then only", this
looks interesting. how did you figire this out? Is there a theorem of this
sort?
>> so time complexity will reduce to O(n * (number of side which can be
largest one for any triplet) ).
unfortunately, in terms of complexity it will still be O(n*n) because
there is no predictive way to find how many elements can be discarded with
above criteria. In fact in the worst case each element may satisfy the prime
factor (with modulo 4 = 1) condition. That said, I agree that it definitely
reduces the average running time.
Thanks,
- Ravindra
On Thu, Oct 20, 2011 at 3:38 PM, anshu mishra <anshumishra6...@gmail.com>wrote:
> @Ravindra
>
> To check the particular number square can be written as sum of two squares
> or not.
>
> If it has any prime factor x such that x % 4 == 1 then only.
>
> Now about time complexity.
>
> suppose u have given array is.
>
> 10 6 13 9 17 4 18 12 1 5.
>
> now u can easily skip the numbers(1, 4, 6, 9, 12, 18);
>
>
> and u have to check only for these numbers(5, 10, 13, 17);
>
> so time complexity will reduce to O(n * (number of side which can be
> largest one for any triplet) ).
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
