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
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
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
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
sravanreddy...@gmail.comwrote:
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.
[algogeeks] Re: Finding non-repetitive element from an Array with complexity n
C'mon guys .
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Fri, Apr 15, 2011 at 5:49 PM, Subhransu subhransu.panigr...@gmail.comwrote:
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.
[algogeeks] Re: Finding non-repetitive element from an Array with complexity n
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.
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 sravanreddy...@gmail.comwrote: 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
@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
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
*@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
subhransu.panigr...@gmail.comwrote:
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 sravanreddy...@gmail.com
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.
[algogeeks] Re: Finding non-repetitive element from an Array with complexity n
@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 subhransu.panigr...@gmail.com 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
sravanreddy...@gmail.comwrote:
@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.
