Jump to content

Unique element


nullArray
 Share

Recommended Posts

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

#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

Link to comment
Share on other sites

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

Any way to trim the fat a bit?

Link to comment
Share on other sites

#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

Link to comment
Share on other sites

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!

Link to comment
Share on other sites

#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 :/.

Link to comment
Share on other sites

That's the riddle I guess.

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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 &lt; 5; i++)
    x = x^nums[i];
cout &lt;&lt; x &lt;&lt; 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)

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...