numbers.
try not to follow brute force method.
--
Vaibhav Jain
--~--~-~--~~~---~--~~
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
questionable. So far my solution
requires a hash table that gives no conflict and can locate a key word
in O(1) time. Otherwise the time complexity will definitely be related
to the number of key words.
Does anyone have idea for a O(N) algorithm to solve this problem?
--
Vaibhav Jain
PROTECTED] wrote:
Thanxs for giving feedback... :-)
Can you please explain how worst case time complexity is O(n*n) of this
solution. Means how u determine this. Plz explain
---
Peeyush Bishnoi
On 8/18/07, Vaibhav Jain [EMAIL PROTECTED] wrote:
hi peeyush,
ur solution is nice
...
Sumedh
On 8/17/07, Vaibhav Jain [EMAIL PROTECTED] wrote:
if u know the range of values stored in array then
let me assume values 1 to k then u can calculate sum of numbers stored
in array in O(n) complexity.
after that apply formula
duplicate value= [k*(k+1)]/2 - sum of numbers
= int[min_in_range - max_in_range + 1]
foreach(i in arrayValues)
if(arrayLookup[i] 0) then
found
else
arrayLookup[i]++
Of course range could be prohibitively large (still constant though if
you know the range before hand).
On 8/17/07, Vaibhav Jain [EMAIL PROTECTED] wrote
only once except for one element that
occurs exactly twice. Is there a way to find this element faster than
O(n*log n) and with constant extra memory? If no, how can I prove it?
Thanks in advance for ideas.
--
Vaibhav Jain
--~--~-~--~~~---~--~~
You received