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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
