DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 326--------------------------------------------------
Re: find the 2 numbers
By: dinesh Date: December 4, 2012, 8:50 am
---------------------------------------------------------
Can you give solution with memory constrain O(1)
#Post#: 349--------------------------------------------------
Re: find the 2 numbers
By: dinesh Date: December 5, 2012, 3:41 am
---------------------------------------------------------
hint: think of bit operations
#Post#: 358--------------------------------------------------
Re: find the 2 numbers
By: srini Date: December 6, 2012, 9:37 am
---------------------------------------------------------
Does XOR operation give the answer??
If all numbers are repeated twice except two, then "XOR"ing all
numbers,(repeated elements will yield in 0) gives us XOR of non
repeated numbers. This is exactly the addition of two numbers.
How to find these two numbers??? Give some hint.
#Post#: 360--------------------------------------------------
Re: find the 2 numbers
By: dinesh Date: December 6, 2012, 10:58 pm
---------------------------------------------------------
try using XOR again!!! ;)
#Post#: 401--------------------------------------------------
Re: find the 2 numbers
By: srini Date: December 10, 2012, 11:34 pm
---------------------------------------------------------
@dinesh: at least now post the answer ::) ::) ::)
#Post#: 402--------------------------------------------------
Re: find the 2 numbers
By: kranthipls Date: December 10, 2012, 11:54 pm
---------------------------------------------------------
Can some one post the answer for this
#Post#: 411--------------------------------------------------
Re: find the 2 numbers
By: dinesh Date: December 11, 2012, 3:57 am
---------------------------------------------------------
Solution for 2 non repeating elements:
Let x and y be the non-repeating elements we are looking for and
arr[] be the input array. First calculate the XOR of all the
array elements.
xor = arr[0]^arr[1]^arr[2].....arr[n-1]
All the bits that are set in xor will be set in one
non-repeating element (x or y) and not in other. So if we take
any set bit of xor and divide the elements of the array in two
sets – one set of elements with same bit set and other set with
same bit not set. By doing so, we will get x in one set and y in
another set. Now if we do XOR of all the elements in first set,
we will get first non-repeating element, and by doing same in
other set we will get the second non-repeating element.
Let us see an example.
arr[] = {2, 4, 7, 9, 2, 4}
1) Get the XOR of all the elements.
xor = 2^4^7^9^2^4 = 14 (1110)
2) Get a number which has only one set bit of the xor.
Since we can easily get the rightmost set bit, let us use it.
set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
Now set_bit_no will have only set as rightmost set bit of
xor.
3) Now divide the elements in two sets and do xor of
elements in each set, and we get the non-repeating
elements 7 and 9. Please see implementation for this
step.
#include <stdio.h>
#include <stdlib.h>
/* This finction sets the values of *x and *y to nonr-epeating
elements in an array arr[] of size n*/
void get2NonRepeatingNos(int arr[], int n, int *x, int *y)
{
int xor = arr[0]; /* Will hold xor of all elements */
int set_bit_no; /* Will have only single set bit of xor */
int i;
*x = 0;
*y = 0;
/* Get the xor of all elements */
for(i = 1; i < n; i++)
xor ^= arr[i];
/* Get the rightmost set bit in set_bit_no */
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 < n; i++)
{
if(arr[i] & set_bit_no)
*x = *x ^ arr[i]; /*XOR of first set */
else
*y = *y ^ arr[i]; /*XOR of second set*/
}
}
/* Driver program to test above function */
int main()
{
int arr[] = {2, 3, 7, 9, 11, 2, 3, 11};
int *x = (int *)malloc(sizeof(int));
int *y = (int *)malloc(sizeof(int));
get2NonRepeatingNos(arr, 8, x, y);
printf("The non-repeating elements are %d and %d", *x, *y);
getchar();
}
Time Complexity: O(n)
Auxiliary Space: O(1)
*****************************************************
DIR Next Page