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
@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
@ 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
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++)
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:
@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
@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[]=