CareerCup

Solution valid for only single pairs

c=0; //temporary variable
for(i=0;i<n;c^=A[i]); //A[1...n]
return c;

c=0; //temporary variable
for(i=0;i<n;c^=A[i]); //A[1...n]
return c;

Assuming loop is OK and we are trying to find different number using XOR.

- if you have pairs of matching numbers aka odd number of elements that just XOR all elements will give result.

- for event number of elements you must remember the first number in a temporary variable, XOR n-1 numbers. If the resulting number is same as first number then return nth number as a different number, else XOR the number and return that as a result.

ex.

int differentNumber(int input[], int n) {
	
	int res = input[0];
	if (n <=2)
		return res;
       
	for (int i = 0; i < n - 2; i++)
		res ^= input[i];
	
        if (n % 2 != 0 ) {
            return (res ^ input[n-1]);
        } else {
            if ( res == input[0]) {
                  return input[n-1];
             } else {
                 return res ^ input[n - 1];
             }	
        }
}

Question not clear. First we cannot traverse array without a loop. Second I guess the question means to use XOR instead of comparison operator to find distinct elements.
Considering this I can only think of the brute force method to find it i.e. O(n^2)

int find_uniq(int *array, int no_of_ele, int pos)
{
int c = 0;
if(no_of_ele == 0)
return 1;
c = array[pos]^array[no_of_ele-1];
if(c != 0 || (pos == no_of_ele-1))
{
return find_uniq(array, no_of_ele-1, pos);
}
else
{
return c;
}
}

int unique_array(int *array, int *u_array, int no_of_ele, int pos1, int pos2)
{
int c = 0;
if(pos1 == no_of_ele)
return pos2;
c = find_uniq(array, no_of_ele, pos1);
printf("%d -> %d\n",array[pos1], c);
if(c != 0)
{
u_array[pos2]=array[pos1];
pos2++;
}
pos1++;
return unique_array(array, u_array, no_of_ele, pos1, pos2);
}

int main()
{
int array[10]= {1,3,6,2,8,9,2,6,4,6};
int uniq_array[10]={};
int i = 0,
uniq_cnt = 0;
uniq_cnt=unique_array(array,uniq_array,10,0,0);
for(i=0; i<10; i++)
{
printf("%d ", array[i]);
}
printf("\n");
for(i=0; i<uniq_cnt; i++)
{
printf("%d ", uniq_array[i]);
}
printf("\n");
return 0;
}

Since it says no loop, interviewer is trying to see if you can think differently. Use Stack :)

I think we can use recursion helper function. Let say number is from I to 10 (n) and 7 is missing.

get the total sum by using (N + (N +1))/2 = 55

Now call the function with Array and index=0 and sum=0 as parameter e.g.
recurse(arr, 0, 0)

call this function till index reaches length of array and store the sum when this function ends compare this sum with sored sum.
r

int find_uniq(int *array, int no_of_ele, int pos)
{
    int c = 0;
    if(no_of_ele == 0)
        return 1;
    c = array[pos]^array[no_of_ele-1];
    if(c != 0 || (pos == no_of_ele-1))
    {
        return find_uniq(array, no_of_ele-1, pos);
    }
    else
    {
        return c;
    }
}

int unique_array(int *array, int *u_array, int no_of_ele, int pos1, int pos2)
{
    int c = 0;
    if(pos1 == no_of_ele)
        return pos2;
    c = find_uniq(array, no_of_ele, pos1);
    printf("%d -> %d\n",array[pos1], c);
    if(c != 0)
    {
        u_array[pos2]=array[pos1];
        pos2++;
    }
    pos1++;
    return unique_array(array, u_array, no_of_ele, pos1, pos2);
}

int main()
{
    int array[10]= {1,3,6,2,8,9,2,6,4,6};
    int uniq_array[10]={};
    int i = 0,
        uniq_cnt = 0;
    uniq_cnt=unique_array(array,uniq_array,10,0,0);
    for(i=0; i<10; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    for(i=0; i<uniq_cnt; i++)
    {
        printf("%d ", uniq_array[i]);
    }
    printf("\n");
    return 0;
}

sort the array and copy it then xor each element

void findDistinct(vector<long>& input, vector<long>& output)
{
	for (vector<long>::const_iterator it = input.begin(); it != input.end(); it++) {
		vector<long>::const_iterator it1 = it + 1;
		for (; it1 != input.end() && (*it ^ *it1); it1++);
		if (it1 == input.end())
			output.push_back(*it);
	}
}

We can traverse an array avoid using loop by recursion.
To me, if the size of the array is not too big, we can take the advantage of memory as this way:
Declare an array (called Counter) with it's INDEX of each element is presented in the given array
By calling recursion, through each element of the given array , we +1 to the Counter of the corresponding ( e.g: inc(Counter[GivenArr[i]]) where i is the runner ).
And using recursion again on the Counter, any value of the Counter equal 1, we write the INDEX.
I now if the value is so discrete, this way won't work well
I am amateur, Thank You for your comments!