@all: First of all apologize for posting the wrong solution. The whole idea behind it was first find the xor of all array elements and this will have xor of only those value which got repeated once and thrice b'cos element which got repeated twice gets nullified. Now intention behind xoring it again was to remove the element which got repeated once. and checking the previous value would catch the element which got repeated thrice which allows us to break through the loop. But for some corner cases it fails. Thanks all of you to bring it to notice. Will work on it to find something better which covers all cases.
On Fri, Jul 9, 2010 at 6:39 AM, Ashish Goel <[email protected]> wrote: > i like the idea whereby when you xor again with all xored, essentially, we > are removing one xor and the result would be the left number(which were > repeated odd number of times) > > however, this will simply not work when > > a] there are multiple single numbers like > 1,2,1,3,1,4,5 > > b] this would need two occurrence of three time repeated numbers to be > adjacent > > eg : for > {5,3,3,1,5,7,7,5,8,8} this won't work > > > > but what i think is that a bit modification of this approach can be used to > identify the numbers which occur odd times > so the new set would be {5,1,5,5} now can we proceed from here, still > thinking... > > > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > On Fri, Jul 9, 2010 at 1:10 AM, Anand <[email protected]> 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 >> <[email protected]>wrote: >> >>> @ any solution less then nlogn would do + O(1) space >>> >>> >>> On Thu, Jul 8, 2010 at 12:38 AM, souravsain <[email protected]>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 <[email protected]> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]<algogeeks%[email protected]> >>>> . >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
