Re: [algogeeks] Re: Array , Number Missing or Duplicate ..
@Dave: Can you please explain it? I am not getting you. -- 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: Array , Number Missing or Duplicate ..
I can think of 2 methods if Hashing is not allowed. 1. Plain comparison of every element with an other element, which takes O(n2) 2. We can sort the array, and the best we could achieve is O(nlogn) after that use simple comparision, like the code here : http://codepad.org/RtRbnyAN; Overall we can optimize it best to O(n) http://codepad.org/RtRbnyAN Best Regards Abhijit On Sun, Feb 27, 2011 at 7:15 PM, Dave dave_and_da...@juno.com wrote: If hashing is disallowed, then I think the best method is to sort the data and check for consecutive triplicates. O(n log n). Dave On Feb 27, 6:35 am, bittu shashank7andr...@gmail.com wrote: @Gaurav Hey I forgot to say Hashing is not allowed sum thing other then this better solution @radha i don't think ur method works here chk out ur methodhttp:// codepad.org/oTDNSoeu Thanks Shashank -- 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: Array , Number Missing or Duplicate ..
We can use count sort for this. Its intermediate step just tell us the frequency of each number. and its complexity is just 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: Array , Number Missing or Duplicate ..
But count sort is not applicable for large number of input.In that case what should be done? -- 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: Array , Number Missing or Duplicate ..
i agree with dave...Sorting seems to be best method until you know something more about type and limitations on the data present...If input has any random numbers then sorting is best if no hashing is permitted... On Sun, Feb 27, 2011 at 7:15 PM, Dave dave_and_da...@juno.com wrote: If hashing is disallowed, then I think the best method is to sort the data and check for consecutive triplicates. O(n log n). Dave On Feb 27, 6:35 am, bittu shashank7andr...@gmail.com wrote: @Gaurav Hey I forgot to say Hashing is not allowed sum thing other then this better solution @radha i don't think ur method works here chk out ur methodhttp:// codepad.org/oTDNSoeu Thanks Shashank -- 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: Array , Number Missing or Duplicate ..
Kind of brute force with O(n*log(n)) map mint, int; for( int i=0; iN; i++) m[a[i]]++; for each element in hashmap if( m[i] == 3) print i; On Sun, Feb 27, 2011 at 3:59 AM, Dave dave_and_da...@juno.com wrote: @Radha: Please explain your method further. You can use this data: 0, 1, 2, 4, 4, 5, 5, 6, 6, 6. Dave On Feb 26, 10:44 am, radha krishnan radhakrishnance...@gmail.com wrote: XOR :P On Sat, Feb 26, 2011 at 10:11 PM, bittu shashank7andr...@gmail.com wrote: Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times. Thanks Shashank -- 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 athttp://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. -- Thanks Regards, Gaurav Gupta Associate Software Engineer IBM Software Lab India Email: gauravgupta[at]in[dot]ibm[dot]com Ph No. : +91-7676-999-350 Quality is never an accident. It is always result of intelligent effort - John Ruskin -- 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.
