@Anand: Awesome solution ,it works even if more than 1 number repeats once...
On 9 July 2010 01:10, Anand <anandut2...@gmail.com> wrote: > One more approach using XOR to find the element repeated thrice. > Complexity: O(n). > Space :0 > > http://codepad.org/p82TGhjR > > main() > { > int arr[]= {5,3,3,1,5,5,7,7,8,8}; > > int len, set_bit_no, x,y,i; > > int xor, prev; > len = sizeof(arr)/sizeof(arr[0]); > > xor = arr[0]; > x = y=0; > > > for(i=1;i<len;i++) > > { > xor ^= arr[i]; > } > > printf("xor:%d\n",xor); > > for(i=0;i<len;i++) > > { > xor ^= arr[i]; > if(xor == 0 && prev == arr[i]) > > { > printf("Found:%d\n", arr[i]); > > break; > } > prev = arr[i]; > > } > } > > > > On Thu, Jul 8, 2010 at 6:46 AM, jalaj jaiswal > <jalaj.jaiswa...@gmail.com>wrote: > >> @ any solution less then nlogn would do + O(1) space >> >> >> On Thu, Jul 8, 2010 at 12:38 AM, souravsain <souravs...@gmail.com> wrote: >> >>> @jalaj >>> >>> Are we looking for a better than )(nlogn) time and O(1) space >>> solution? What if our target? >>> >>> If a solution is required simple, then as mentioned by Satya, sort the >>> numbers in O(nlogn) time and scan once in O(n) time. So we get the >>> number repeated 3 times in O(nlogn) time and O(1) space. >>> >>> Sourav >>> >>> On Jul 7, 7:36 pm, Priyanka Chatterjee <dona.1...@gmail.com> wrote: >>> > > I am sceptical whether any XOR solution exits for your question. But >>> if >>> > > the question is modified as : >>> > >>> > > *Only one number repeats once,* some no.s repeat twice and only one >>> number >>> > > repeat thrice, here is the XOR solution for that. >>> > >>> > > suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8} >>> > > in the example 1 repeats once and 5 repeats thrice. >>> > >>> > > 1>let T= XOR( all elements)= 1^5. (all elements occurring even no of >>> times >>> > > nullify) -O(N) >>> > >>> > > ( let x=1, y=5 >>> > > As we know the no. repeating once and the no. repeating thrice are >>> unequal, >>> > > there must exist some bit 'k' such that x[k]!=y[k]. There may be more >>> than >>> > > such bits in x and y. But one such bit certainly yields T[k]=1 after >>> x^y) >>> > >>> > > 2> Now traverse along each bit of T( in binary) from left or right >>> and >>> > > consider T[i] =1 which is encountered first. store it . let b=i; >>> > > (O(M) time and O(M) space to store binary if M is the bit length of >>> T.) >>> > >>> > > 3> T1= XOR(all elements in given array having bit b as 1)..... (O(N) >>> time >>> > > and O(M) space) ( time is O(MN) but as M<=32 , complexity remain >>> O(N)) >>> > >>> > > 4> T0= XOR( all elements in given array having bit b as 0) (O(N) time >>> and >>> > > O(M) space) >>> > >>> > > One of (T1,T0) gives the no. that repeats once and the other gives >>> the no >>> > > that repeats thrice. >>> > >>> > > 6> Now traverse the along array A and compute count for T1 and T0. >>> The >>> > > count that equals 3 gives the corresponding no. repeating thrice. >>> -O(N) >>> > >>> > > Time complexity is O(N+M) . Linear >>> > > space complexity is O(M) to store binary form. >>> > >>> > > But this algo certainly fails if more than one no. repeats once. >>> > >>> > -- >>> > Thanks & Regards, >>> > Priyanka Chatterjee >>> > Final Year Undergraduate Student, >>> > Computer Science & Engineering, >>> > National Institute Of Technology,Durgapur >>> > Indiahttp://priyanka-nit.blogspot.com/- 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> With Regards, >> Jalaj Jaiswal >> +919026283397 >> B.TECH IT >> IIIT ALLAHABAD >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks & Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science & Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
