yes correct...missed that :( , But we can use method given in the above
geekforgeeks link to find those 2 elements :
set_bit_no = xor & ~(xor-1);
/* Now divide elements in two sets by comparing rightmost set
bit of xor with bit at same position in each element. */
for(i = 0; i < size; i++)
{
if(arr[i] & set_bit_no)
x = x ^ arr[i]; /*XOR of first set in arr[] */
else
y = y ^ arr[i]; /*XOR of second set in arr[] */
}
for(i = 1; i <= n; i++)
{
if(i & set_bit_no)
x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
else
y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
}
printf("\n The two repeating elements are %d & %d ", x, y);
now we just need to check if any of these two elements found is present in
the given array , if yes then other element in the missing one.
On Mon, Nov 19, 2012 at 12:07 PM, Rushiraj Patel <[email protected]>wrote:
> @atul : In the second for loop.......temp will also contain one which is
> being missing along with the one which is being repeated.....
> kindly check it once again.
>
>
> On Mon, Nov 19, 2012 at 11:44 AM, atul anand <[email protected]>wrote:
>
>> array has all distinct elements ans lie b/w 1 to n , now bcozz they are
>> all distinct except 1 element means it should have all element with range 1
>> to n...except 1 element , which can be any element b/w 1 to n.
>> temp=arr[0]
>> *for i=1 to n
>> temp=temp^arr[i]; *
>> //now temp will contain all distinct elements except one which is
>> repeated(they cancel out)
>> *for i=1 to n
>> temp=temp ^ i; *
>> // now this will cancel out distinct elements excluding one which is
>> repeated.
>> temp will contain that repeated element
>>
>> On Sun, Nov 18, 2012 at 7:31 PM, shady <[email protected]> wrote:
>>
>>> Given an array of size n, which has all distinct elements between 1 to n
>>> with one element repeating, which also implies that one element is missing.
>>> How to find the repeating element without using extra space and linear
>>> time complexity ?
>>>
>>> Any way to do it with exor ? :P
>>>
>>> --
>>>
>>>
>>>
>>
>> --
>>
>>
>>
>
> --
>
>
>
--
