Unique element

[nullArray]

I have an odd number of elements.

Only one is unique.

How do I find it?

I have this right now, but it only removes 1 duplicate, not two.

#include <iostream>

using namespace std;
const int arrayLen = 13;


int main (int argc, char * const argv[]) 
{
    int array[arrayLen]={0,0,1,1,2,2,3,3,4,4,5,6,6};
    int i,t,j,k;
    
    for(i = 1; i < arrayLen; i++)
    {
        t += array[i];
        
        for(i = 1, k = 1, j = i + 1; j <= arrayLen; j++)
        {
            if (t - array[i] == t - array[j])
                continue;
                
            k++;
            array[k] = array[j];
            i = j;
        }
    }
    for(i = 1; i <= k; i++)
        cout << array[i] <<  " ";                
    
}

5 is the unique element here. I had something I wrote myself earlier, but I kept getting segmentation faults when I made my array larger than 11 and couldn't for the life of me, figure out why. I lifted this code from some website and am looking to alter it.

Thanks for the help.

EDIT: This is just an example, a demo..., it's going to be something bigger later. So it doesn't need to be overly complicated or anything.

[Jonnycake]

I'd make it create 2 arrays and each time you go over a unique value, add it to the array. In pseudo-code it might be something like this:

Let x=0
Let y=0
Let z=0
Let invalid=0
Let array={0,0,1,1,2,2,3,3,4,4,5,6,6}
Let array2={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

While x<len
     Do
            While y<len and array2[y]!=-1
                   Do
                          if array[x]==array2[y]
                                 Then
                                       Invalid=1
                                       break
                          End
              End
              If invalid!=1
                      Then
                              array2[z]=array[x]
                              x=x+1
               End
               Invalid=0
             x=x+1
End
x=0
While x<len and array2[x]!=-1
         Do
                 Print array2[x]
                x=x+1
End

Edit:

This will find all of the unique elements (or at least it should when written in the right syntax and stuff), if you want to just find one unique, you can have a break after you check that invalid is not equal to 1

[nullArray]

So something like this?

#include <iostream>

using namespace std;
const int arrayLen = 13;


int main (int argc, char * const argv[]) 
{
    int array[arrayLen]={0,0,1,1,2,2,3,3,4,4,5,6,6};
    int unique[arrayLen]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
    int x = 0, y = 0, z = 0, invalid = 0;
    
    while (x < arrayLen)
    {
        while ((y < arrayLen) && (unique[y] != -1))
        {
            if(array[x] == unique[y])
            {
                invalid = 1;
                cout << endl << "I'm stuck here" << endl;
                break;
            }
        }
        if (invalid != 1)
        {
            unique[z] = array[x];
            cout << endl << "Actually, I'm stuck here" << endl;
            x++;
            break;
        }
        else
        {
            invalid = 0;
            x++;
        }
        
    }
    
    x = 0;
    while ((x < arrayLen) && (unique[x] != -1))
    {
        cout << endl << "Do I even get here?" << endl;
        cout << unique[x] << " ";
        x++;
    }
    
}

It doesn't seem to work...,

output:

Actually, I'm stuck here

Do I even get here?
0 logout

[Process completed]

EDIT: Thanks a lot for helping me, btw.

[Jonnycake]

#include <stdio.h>

int main()
{
        int array[13]={0,0,1,1,2,2,3,3,4,4,5,6,6};
        int array2[13]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
        int unique[13]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
        int v=0,w=0, x = 0, y = 0, z = 0, invalid = 0;

        for(x=0;x<13;x++) // array
        {
                for(y=0;y<13;y++) // array2
                {
                        if(array[x]==array2[y])
                                invalid=1;
                }
                if(invalid==0)
                {
                        for(v=0;v<13;v++)
                        {
                                if(unique[v]==array[x])
                                {
                                        unique[v]=-1;
                                        invalid=1;
                                }
                        }
                        if(invalid==0)
                        {
                                unique[w++]=array[x];
                        }
                }
                else
                {
                        for(v=0;v<13;v++)
                        {
                                if(unique[v]==array[x])
                                        unique[v]=-1;
                        }
                }
                invalid=0;
        }

        for(x=0;x<13;x++)
        {
                if(unique[x]!=-1)
                        printf("%d\n",unique[x]);
        }
}

There's what I have in C, I think I messed up on the pseudocode a lot.

Edit:

btw, I have no clue how it's even getting to the else statement since I'm not setting anything in array2[] or at least I don't think I am lol

[nullArray]

Well, It's woefully convoluted, but it works...,

Any way to trim the fat a bit?

[Jonnycake]

#include <stdio.h>

int main()
{
        int array[13]={0,0,1,1,2,2,3,3,4,4,5,6,6};
        int array2[13],unique[13]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
        int v,w,x,y,z,invalid=0;

        for(x=0;x<13;x++) // array
        {
                for(y=0;y<13;y++) // array2
                        if(array[x]==array2[y] || array[x]==unique[y])
                        {
                                invalid=1;
                                if(unique[y]==array[x])
                                        unique[y]=-1;
                        }
                if(invalid==0)
                        unique[w++]=array[x];
                invalid=0;
        }

        for(x=0;x<13;x++)
                if(unique[x]!=-1)
                        printf("%d\n",unique[x]);
}

That should work as well. Much shorter :P

[nullArray]

Actually, I'm being told that it's possible with one variable, runs in linear time and takes advantage of the XOR operation.

Now I'm perplexed.

EDIT: And it doesn't have to be sorted either..., that's the biggie!

[Jonnycake]

#include <stdio.h>

int main()
{
        int x,y,invalid;
        int array[13]={0,0,1,1,2,2,3,3,4,4,5,6,6};
        for(x=0;x<13;x++)
        {
                for(y=0;y<13;y++)
                        if(y!=x && array[x]==array[y])
                                invalid=1;
                if(invalid!=1)
                        printf("%d\n",array[x]);
                invalid=0;
        }
}

That's about as short as I can get it and I can't think of a way to make it any different lol.

Editz0r:

Did you ask them for an example of how they could do that? I see no way of only using one variable with XOR :/.

[nullArray]

That's the riddle I guess.

I'm going crazy! The tantilizing hints don't help either!

[Jonnycake]

Yeah, really. Did you figure it out yet? I'm starting to wonder about it too! lol

Edit:

Ooooooooh, found it!!!! http://blog.arahul.in/2008/06/find-duplicate-element.html

Edit2:

But that only finds one non-duplicate element. That's what's wrong with it lol.

Edit3:

Also, if I'm thinking correctly, if there's a number that shows up an odd number of times, it won't get canceled out and end up being output as the non-duplicate element and if there's no non-duplicate elements, it will output 0 which in most cases is not desirable.

[nullArray]

Yeah, really. Did you figure it out yet? I'm starting to wonder about it too! lol

Edit:

Ooooooooh, found it!!!! http://blog.arahul.in/2008/06/find-duplicate-element.html

Edit2:

But that only finds one non-duplicate element. That's what's wrong with it lol.

Edit3:

Also, if I'm thinking correctly, if there's a number that shows up an odd number of times, it won't get canceled out and end up being output as the non-duplicate element and if there's no non-duplicate elements, it will output 0 which in most cases is not desirable.

You found it. This is the exact problem.

[nullArray]

Hmm, so I implemented it and it works flawlessly, but I still don't totally understand how it works. I get what xor does ( 01/10 = true 00/11 = false) but I don't get how it can eliminate elements on one pass without knowing where the other one is.

[Jonnycake]

Xor does it bit by bit with the binary.

xor 001 with 001:

001

^001

------

000

You xor bit by bit. The xor of an integer as:

binary[8]={0,0,0,0,0,0,0,1};
binary2[8]={0,0,0,0,0,0,0,1};
int x;
for(x=0;x<8;x++)
     binary[x]^binary2[x];

That's doing xor 1^1.

[OneTimePad]

How it works:

if you have two integers, x and y, x^y will return an integer such that each bit will be 0 if the corresponding bits from x and y are the same, and 1 if they are different. This leads to two properties: z = x^x == 0, because every bit is the same, and z = x^0 == x, because when nth bit of x is 1, it is different from 0, therefor the nth bit of z is 1, and when the nth bit of x is 0, it is the same as 0, therefor the nth bit of z is 0.

Ex:

5^4 = 0b101^0b100 = 0b001 = 1 <-- only the last bit is different

7^9 = 0b0111^0b1001 = 0b1110 = 14 <-- the first three bits are different

7^0 = 0b111^0b000 = 0b111 = 7 <--only the bits that are 1 (all three) are different

8^0 = 0b1000^0b0000 = 0b1000 = 8 <-- only the bits that are 1 (the first) are different

6^6 = 0b110^0b110 = 0b000 = 0 <-- no bits are different

So, if you traverse an array, and xor each item with the cumulative xor of the previous, any duplicates will cancel out:

int nums[5] = {1,1,2,2,3};
int i, x = 0;
for(i = 0; i < 5; i++)
    x = x^nums[i];
cout << x << endl;

results in:

x = 1^1^2^2^3 = (1^1)^(2^2)^3 = 0^0^3 = 0^3 = 3

Note: this will work so long as 1) there is only ONE unique number (otherwise, it will return the xor of all unique elements), and 2) any duplicate elements have an even number of elements (they cancel out in pairs, and any remaining numbers would 'pollute' the output)