Re: [algogeeks] Re: Element in Array Repeated Even Number of Times
@Dave : Please specify reason for choosing radix sort ? On Thu, Sep 8, 2011 at 7:02 AM, Sandy sandy.wad...@gmail.com wrote: Thanks Dave, Piyush, and Bittursk. On Wed, Sep 7, 2011 at 2:48 PM, Dave dave_and_da...@juno.com wrote: @Sandy: It can be done in O(n) time with O(n) extra space by sorting the data with a radix sort and then scanning the array for the element you are seeking. Dave On Sep 7, 11:43 am, Sandy sandy.wad...@gmail.com wrote: You have an array in which every number is repeated odd number of times except one. Write a function to find that one element in O(n) time. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- 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. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- 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: Element in Array Repeated Even Number of Times
O(kN) where k is the length of the numbers which are assumed to be integers, so for even k = 100 it is O(N). On Fri, Sep 9, 2011 at 4:27 PM, Pritpal Singh pritpal2...@gmail.com wrote: @Dave : Please specify reason for choosing radix sort ? On Thu, Sep 8, 2011 at 7:02 AM, Sandy sandy.wad...@gmail.com wrote: Thanks Dave, Piyush, and Bittursk. On Wed, Sep 7, 2011 at 2:48 PM, Dave dave_and_da...@juno.com wrote: @Sandy: It can be done in O(n) time with O(n) extra space by sorting the data with a radix sort and then scanning the array for the element you are seeking. Dave On Sep 7, 11:43 am, Sandy sandy.wad...@gmail.com wrote: You have an array in which every number is repeated odd number of times except one. Write a function to find that one element in O(n) time. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- 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. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- 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. -- 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: Element in Array Repeated Even Number of Times
are all the numbers in a range?? say from (1 to n) and is there atleast one occurence of each?? On Fri, Sep 9, 2011 at 5:25 PM, shady sinv...@gmail.com wrote: O(kN) where k is the length of the numbers which are assumed to be integers, so for even k = 100 it is O(N). On Fri, Sep 9, 2011 at 4:27 PM, Pritpal Singh pritpal2...@gmail.comwrote: @Dave : Please specify reason for choosing radix sort ? On Thu, Sep 8, 2011 at 7:02 AM, Sandy sandy.wad...@gmail.com wrote: Thanks Dave, Piyush, and Bittursk. On Wed, Sep 7, 2011 at 2:48 PM, Dave dave_and_da...@juno.com wrote: @Sandy: It can be done in O(n) time with O(n) extra space by sorting the data with a radix sort and then scanning the array for the element you are seeking. Dave On Sep 7, 11:43 am, Sandy sandy.wad...@gmail.com wrote: You have an array in which every number is repeated odd number of times except one. Write a function to find that one element in O(n) time. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- 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. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- 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. -- 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: Element in Array Repeated Even Number of Times
@Rahul - Can you explain the logic and complexity? On Wed, Sep 7, 2011 at 11:06 PM, Rahul Thankachan rahul29ma...@gmail.comwrote: On Sep 7, 12:43 pm, Sandy sandy.wad...@gmail.com wrote: You have an array in which every number is repeated odd number of times except one. Write a function to find that one element in O(n) time. -- *Sandeep Kumar,* ( Mobile+91-9866507368begin_of_the_skype_highlighting +91-9866507368 *“I believe in smart work, Believe Me”* sry i made the logic for the opp for even instead..u just need to change sm values...u will get it :):) its simple.. -- 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. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- 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: Element in Array Repeated Even Number of Times
i don't think it's of O(n) for even it's actually easy. Take the xor of all the elements you will left with the element which appears odd number of times. O(n) but for the odd case, we need to use extra space. Use hash map to keep the count of each number and take the odd one out, i mean the even one. On Wed, Sep 7, 2011 at 11:06 PM, Rahul Thankachan rahul29ma...@gmail.comwrote: On Sep 7, 12:43 pm, Sandy sandy.wad...@gmail.com wrote: You have an array in which every number is repeated odd number of times except one. Write a function to find that one element in O(n) time. -- *Sandeep Kumar,* ( Mobile+91-9866507368begin_of_the_skype_highlighting +91-9866507368 *“I believe in smart work, Believe Me”* sry i made the logic for the opp for even instead..u just need to change sm values...u will get it :):) its simple.. -- 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: Element in Array Repeated Even Number of Times
It can be done in O(n) time using a hash table as shown by the following pseudo code: function FindEvenRepeter(arr[]) hash_table = empty sum = 0 for x in arr if (x is present in hash_table) sum = sum ^ x else add x to hash_table return sum As Piyush correctly said, using XOR operation we can find a number that repeats odd number of times in an array in which other numbers repeat even number of times. So we try to reduce the given problem to the simplified problem. To do this, I have ignored the 1st occurance of any integer by storing it into the hash table and XORing the rest of the occurances. What this does is that, now the odd number of times occurring integers occur even number of times and get cancelled out by the XOR operation and the only number occuring even number of times, now gets XORed odd number of times, resulting in the final value of sum to be the required number Time complexity is as apparent O(n) coz adding and searching to and in a hash table is O(1) operation. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Uwcv0-FYGjcJ. 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.
