Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
to get the non repeating element we have to travese array atleast once.so
Time complixity has to minimum o(n).as I suppose..
The XOr solution will fail because odd number will be there...
Hashing itself require o(n) space in worst case.
On Mon, Apr 18, 2011 at 12:40 AM, sravanreddy001
wrote:
> can u explain ur solution with one of these sets?
>
> {1,2,1,3,2,1}
> {1,2,1,3,2,2}
>
> an element can repeat for any number of times >= 2
>
> --
> 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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
can u explain ur solution with one of these sets?
{1,2,1,3,2,1}
{1,2,1,3,2,2}
an element can repeat for any number of times >= 2
--
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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
I think ,Gunjan's solution is right.
suppose {1,2,1,3,2} is given,
1 --- 01
2 10
3 - 11
..
..
..
So XOR these elements 01 XOR 10 ---> 11
11 XOR 01 ---> 10
10 XOR 11 ---> 01
01 XOR 10 ---> 11(3)
So answer is 3.
Any query???
--
Thanks and Regards,
Manish Pathak **
TimesJobs.com
Mo. 9015687266
--
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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
@subharansu When I meant the n/2 space in worst case, assuming u have 1 million total numbers(n), and according to the problem, it can have single non-repitive number. soo.. 99 entires will comprise of at max 99/2 values.. assumuing.. none of them repeated more than twice Actaully.. I was not considering the additional space to store the counts, with out that its n/2 space.. anyway.. if its n/2 or n... its O(n) -- 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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
@Dave:
It can have multiple values(twice, thrice,. . . ).
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Sun, Apr 17, 2011 at 1:06 AM, Dave wrote:
> @Subhransu: Your description and new example still leave open the
> question of whether "repetative" means "occurs exactly twice" or
> "occurs twice or more." So, does A(1,2,2,3,3,3) fall within or without
> your intended problem? If "occurs exactly twice" is your meaning, then
> the xor method proposed by Gunjan Sharma is a solution.
>
> Dave
>
> On Apr 16, 1:27 pm, Subhransu wrote:
> > Rephrasing the array to reflect one non-repetative element. Inconvenience
> > regretted.
> > A{1, 1024, 2 , 1, 2, *3*, 4, 4, 1024}.
> > Now there only one non-repetative element "3"...
> >
> > *Subhransu Panigrahi
> > *
> > *Mobile:* *+91-9840931538*
> > *Email:* subhransu.panigr...@gmail.com
> >
> > On Sat, Apr 16, 2011 at 11:39 PM, sravanreddy001
> > wrote:
> >
> >
> >
> > > @shadow.. your approach fails if the same number has odd number of
> > > occurances...
> >
> > > --
> > > 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.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> 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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
*@sravanreddy001:
*What i can presume from your solution is , correct me if i am wrong
If the array has n elements (including the repetitive) where you will
create at worst n/2 variable to keep track and counting the number. Lets say
the array can have 1M.
or you want to mean something else ?
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Sat, Apr 16, 2011 at 11:57 PM, Subhransu
wrote:
> Rephrasing the array to reflect one non-repetative element. Inconvenience
> regretted.
> A{1, 1024, 2 , 1, 2, *3*, 4, 4, 1024}.
> Now there only one non-repetative element "3"...
>
>
> *Subhransu Panigrahi
> *
> *Mobile:* *+91-9840931538*
> *Email:* subhransu.panigr...@gmail.com
>
>
>
> On Sat, Apr 16, 2011 at 11:39 PM, sravanreddy001 > wrote:
>
>> @shadow.. your approach fails if the same number has odd number of
>> occurances...
>>
>> --
>> 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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
Rephrasing the array to reflect one non-repetative element. Inconvenience
regretted.
A{1, 1024, 2 , 1, 2, *3*, 4, 4, 1024}.
Now there only one non-repetative element "3"...
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Sat, Apr 16, 2011 at 11:39 PM, sravanreddy001
wrote:
> @shadow.. your approach fails if the same number has odd number of
> occurances...
>
> --
> 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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
Yeah right solution taken back :P -- 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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
@shadow.. your approach fails if the same number has odd number of occurances... -- 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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
Assuming only one non-repeating element just run over the n elements and keep xoring only the non repeated one will be left. O(1) space, O(n) time On Sat, Apr 16, 2011 at 11:34 PM, sravanreddy001 wrote: > Assuming there is only one element which i not repeated, > > my approach will need O(n) space... > load all distinct elements and they counts as you traverse them first.. > cost = O(n) > > searching an element from this.. O(n) > > any better memory management here(i mean space) > > -- > 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. > -- Regards Gunjan Sharma Chairman IEEE Students Chapter IIT Roorkee B.Tech IV year CSE Contact No- +91 9997767077 -- 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.
Re: [algogeeks] Re: Finding non-repetitive element from an Array with complexity n
There are two elements that do not repeat in ur array which one to give.
On Sat, Apr 16, 2011 at 7:23 PM, Subhransu wrote:
> C'mon guys .
>
> *Subhransu Panigrahi
> *
> *Mobile:* *+91-9840931538*
> *Email:* subhransu.panigr...@gmail.com
>
>
>
> On Fri, Apr 15, 2011 at 5:49 PM, Subhransu
> wrote:
>
>> Hey Geeks,
>>
>> Though there are multiple algo to find an element but with a complexity of
>> O(N),
>> How to find NON-repetitive element from an array also best effective
>> memory/space complexity as well.
>>
>> Lets say an array is A{1, 1024, 2 , 1, 2, 3, 4, 4 }
>> The output has to be foundout "3" with complexity n.
>>
>> *Subhransu Panigrahi
>> *
>> *Mobile:* *+91-9840931538*
>> *Email:* subhransu.panigr...@gmail.com
>>
>
> --
> 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.
>
--
Regards
Gunjan Sharma
Chairman IEEE Students Chapter IIT Roorkee
B.Tech IV year CSE
Contact No- +91 9997767077
--
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.
