Re: [algogeeks] Re: adobe problem---array

2010-07-09 Thread Ashish Goel
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 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;ilen;i++)

   {
 xor ^= arr[i];
   }

   printf(xor:%d\n,xor);

   for(i=0;ilen;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.comwrote:

 @ 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.
 
   1let 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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 

Re: [algogeeks] Re: adobe problem---array

2010-07-09 Thread Anand
@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 ashg...@gmail.com 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 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;ilen;i++)

   {
 xor ^= arr[i];
   }

   printf(xor:%d\n,xor);

   for(i=0;ilen;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.comwrote:

 @ any solution less then nlogn would do + O(1) space


 On Thu, Jul 8, 2010 at 12:38 AM, souravsain souravs...@gmail.comwrote:

 @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.
 
   1let 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.comalgogeeks%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 

Re: [algogeeks] Re: adobe problem---array

2010-07-08 Thread jalaj jaiswal
@ 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.
 
   1let 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.comalgogeeks%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.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



Re: [algogeeks] Re: adobe problem---array

2010-07-08 Thread Anand
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;ilen;i++)
  {
xor ^= arr[i];
  }

  printf(xor:%d\n,xor);

  for(i=0;ilen;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.comwrote:

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



Re: [algogeeks] Re: adobe problem---array

2010-07-08 Thread Amit Jaspal
Then do a inplace merge sort / a quick sort and then get a number which
repeats 3 times

On Thu, Jul 8, 2010 at 7:16 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:

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



Re: [algogeeks] Re: adobe problem---array

2010-07-08 Thread Jitendra Kushwaha
@anand
Your code wont work for many of the cases
int arr[]= {5,3,1,11,5,7,11,5,8};

please check the correctness before posting any solution

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



Re: [algogeeks] Re: adobe problem---array

2010-07-08 Thread Priyanka Chatterjee
@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;ilen;i++)

   {
 xor ^= arr[i];
   }

   printf(xor:%d\n,xor);

   for(i=0;ilen;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.comwrote:

 @ 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.
 
   1let 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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.