Find unique numbers in array

Question

Well, I have to find how many different numbers are in an array.

For example if array is: 1 9 4 5 8 3 1 3 5

The output should be 6, because 1,9,4,5,8,3 are unique and 1,3,5 are repeating (not unique).

So, here is my code so far..... not working properly thought.

#include <iostream>

using namespace std;

int main() {
    int r = 0, a[50], n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < j; k++) {
            if (a[k] != a[j]) r++;
        }
    }
    cout << r << endl;
    return 0;
}

Sort the array, then it's trivial. Try to figure out for yourself how the complexity of that compares to the complexity of your solution. — Kerrek SB, Feb 06 '13 at 23:31
This seems like homework to me... but yes, you can sort the array, or you can use a hashtable. — Reinderien, Feb 06 '13 at 23:32
seems SO is a good place to get last minute homework done. format question, post it on SO, ???, get answer! — thang, Feb 07 '13 at 00:11
@thang: Seems it's not - considering that nearly all answers to this questions have either an incorrect algorithm or use the standard library to do the job - which apparently is not what this homework is about ... — JoergB, Feb 08 '13 at 10:46
This is the best logic I ever found.http://stackoverflow.com/questions/28320454/can-xor-of-two-integers-go-out-of-bounds — Rasmi Ranjan Nayak, Feb 04 '15 at 14:22

Branko Dimitrijevic · Answer 1 · 2013-02-07T00:01:29.077

Let me join the party ;)

You could also use a hash-table:

#include <unordered_set>
#include <iostream>

int main() {

    int a[] = { 1, 9, 4, 5, 8, 3, 1, 3, 5 };
    const size_t len = sizeof(a) / sizeof(a[0]);

    std::unordered_set<int> s(a, a + len);

    std::cout << s.size() << std::endl;
    return EXIT_SUCCESS;

}

Not that it matters here, but this will likely have the best performance for large arrays.

If the difference between smallest and greatest element is reasonably small, then you could do something even faster:

Create a vector<bool> that spans the range between min and max element (if you knew the array elements at compile-time, I'd suggest the std::bitset instead, but then you could just compute everything in the compile-time using template meta-programming anyway).
For each element of the input array, set the corresponding flag in vector<bool>.
Once you are done, simply count the number of trues in the vector<bool>.

Thanks for your help, although this is not very basic, I appreciate your help. — user2041143, Feb 07 '13 at 00:06

score 11 · Answer 2 · answered Feb 06 '13 at 23:38

11

A std::set contains only unique elements already.

#include <set>

int main()
{
    int a[] = { 1, 9, 4, 5, 8, 3, 1, 3, 5 };

    std::set<int> sa(a, a + 9);
    std::cout << sa.size() << std::endl;
}

answered Feb 06 '13 at 23:38

dreamlax

93,976
29
161
209

is "9" the number of entries or the highest value? – Ben Jan 12 '19 at 16:19
1

@Ben no, it's the size of an array – udit043 Mar 03 '19 at 18:31

score 4 · Answer 3 · edited Feb 06 '13 at 23:49

4

How about this?

#include <list>

int main()
{
    int a[] = {1, 9, 4, 5, 8, 3, 1, 3, 5};

    std::list<int> la(a, a+9);
    la.sort();
    la.unique();
    std::cout << la.size() << std::endl;

    return 0;
}

edited Feb 06 '13 at 23:49

David G

94,763
41
167
253

answered Feb 06 '13 at 23:35

billz

44,644
9
83
100

1

You also could have used `std::set` :P – Rapptz Feb 06 '13 at 23:36
Well, my problem is that I haven't studied vectors yet and I have to make this using loops / arrays only. Any help with that? – user2041143 Feb 06 '13 at 23:45
You need to sort it first, then count adjacent elements. – billz Feb 06 '13 at 23:45
Is the correctness of the la.unique() method predicated on firstly running sort()? – Nicholas Hamilton May 18 '14 at 11:01

Nik Bougalis · Answer 4 · 2013-02-08T14:44:48.377

Since you've stated that you cannot use the standard library and must use loops, let's try this solution instead.

#include <iostream>

using namespace std; // you're a bad, bad boy!

int main() 
{
    int r = 0, a[50], n;

    cout << "How many numbers will you input? ";
    cin >> n;

    if(n <= 0)
    {
        cout << "What? Put me in Coach. I'm ready! I can do this!" << endl;
        return -1;
    }

    if(n > 50)
    {
        cout << "So many numbers! I... can't do this Coach!" << endl;
        return -1;
    }   

    cout << "OK... Enter your numbers now." << endl;

    for (int i = 0; i < n; i++)
        cin >> a[i];


    cout << "Let's see... ";

    // We could sort the list but that's a bit too much. We will choose the
    // naive approach which is O(n^2), but that's OK. We're still learning!

    for (int i = 0; i != n; i++) 
    { // Go through the list once.      
        for (int j = 0; j != i; j++)
        { // And check if this number has already appeared in the list:
            if((i != j) && (a[j] == a[i]))
            { // A duplicate number!        
                r++; 
                break;
            }
        }
    }

    cout << "I count " << n - r << " unique numbers!" << endl;

    return 0;
}

I urge you to not submit this code as your homework - at least not without understanding it. You will only do yourself a disservice, and chances are that your instructor will know that you didn't write it anyways: I've been a grader before, and it's fairly obvious when someone's code quality magically improves.

This solves a different problem: it counts the values that occur exactly once, not all different values. — JoergB, Feb 08 '13 at 10:40
@joergb You are wrong. Read the code again - and tell me what `n - r` calculates. It's really not difficult to figure it out; you can even *run* the code if you must. — Nik Bougalis, Feb 08 '13 at 13:58
I read the code again, I now even ran it against the test input of the OP: with that input it returns `3`, not `6` as for the specified problem. It is as I said: your code counts numbers that occur only once. `r` counts all instances of numbers that occur repeatedly - even the first. The OP wanted a count of *all* different numbers. The solutions using std::set or std:: list get that right. — JoergB, Feb 08 '13 at 14:17
Oh wow, you're right. I totally misread the problem. Will tweak the code. — Nik Bougalis, Feb 08 '13 at 14:40

score 0 · Answer 5 · answered Feb 06 '13 at 23:39

0

I think the location for increasing the value of r is incorrect

#include <iostream>
using namespace std;

int main()
{
    int r=0,a[50],n;
    cin >>n;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    for (int j=0;j<n;j++)
    {   
        bool flag = true;  
        for(int k=;k<j;k++)
        {
            if(a[k]!=a[j])
            {
               flag = false;
               break;
            }
       }
       if (true == flag) 
       {
           r++;
       }
    }
    cout << r << endl;
    return 0;
}

However, my suggestion is using more sophisticated algorithms (this algorithm has O(N^2)).

answered Feb 06 '13 at 23:39

iampat

1,072
1
12
23

1

O(n^2) complexity *and* `if (true == flag)`? The latter is particularly scary. – dreamlax Feb 06 '13 at 23:42
No, I meant, can't you figure out why it's not working as intended? – Nik Bougalis Feb 07 '13 at 00:14
Not really, especially with booleans I got even more confused. – user2041143 Feb 07 '13 at 00:16
The problem is not in the booleans. It is in the main condition. If you rename `flag` to have a name that tells what it means, you might spot it. – JoergB Feb 08 '13 at 10:43

cameronjchurch · Answer 6 · 2013-02-07T00:18:24.280

this should work, however its probably not the optimum solution.

#include <iostream>

using namespace std;

int main()
{
int a[50],n;        
int uniqueNumbers; // this will be the total numbers entered and we will -- it
cin >>n;    
uniqueNumbers = n;  
for(int i=0;i<n;i++)
{
    cin >> a[i];
}   
for (int j=0;j<n;j++)
{   
    for(int k=0;k<n;k++)
    {
        /* 
        the and clause below is what I think you were missing.
        you were probably getting false positatives when j == k because a[1] will always == a[1] ;-)
        */
        if((a[k] == a[j]) && (k!=j)) 
        { uniqueNumebers--; }
    }       
}
cout << uniqueNumbers << endl;
return 0;
}

rashedcs · Answer 7 · 2017-07-08T15:47:02.687

0

We can use C++ STL vector in this program .

  int main() 
  {
    int a[] = {1, 9, 4, 5, 8, 3, 1, 3, 5};
    vector<int>v(a, a+9);

    sort(v.begin(), v.end()); 
    v.erase(unique(v.begin(), v.end()), v.end()); 

    cout<<v.size()<<endl;

    return 0;
  }

edited Jul 08 '17 at 15:47

answered Mar 09 '17 at 05:43

rashedcs

3,588
2
39
40

score 0 · Answer 8 · answered Feb 25 '18 at 01:47

Please dry run your code See in the outer for loop for each element it is counted more than one inside inner loop.let us say the loop contains 1,2,3,4.1.....elements dry run it in the second iteration and third iteration 1 is counted because 1 is 1!=2 as well as 1!=3

Now solution time!!

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
ll arr[1000007]={0};
int main()
{
  ios_base::sync_with_stdio(false);//used for fast i/o
    ll n;cin>>n;
      for(ll i=1;i<=n;i++)
        cin>>arr[i];

        sort(arr,arr+n);

       ll cnt=0;
                for(ll i=1;i<=n-1;i++)
                  {
                   if(arr[i+1]-arr[i]==0)
                     cnt++;
                  }
                 cout<<n-cnt<<endl;


  cin.tie(NULL);
  return 0;
}

score 0 · Answer 9 · edited May 06 '23 at 00:52

0

Not as graceful as using set but works 1.4 times faster

int a[] = {1, 9, 4, 5, 8, 3, 1, 3, 5}

std::map<int, char> m;

for (int i = 0; i < 9; i++) {
    if ( m.count(a[i]) == 0 )
        m.insert( pair<int, char>(a[i], 0x00) );
}

Keys in map m presents list of unique values in array a

edited May 06 '23 at 00:52

user16217248

3,119
19
19
37

answered May 02 '23 at 17:17

Alexander Zyuzin

1
1

score -1 · Answer 10 · edited Mar 19 '22 at 01:06

#include<bits/stdc++.h> using namespace std;

int find_unique(int arr[], int size){

    int ans = 0;
    for(int i = 0; i < size; i++){
        ans = ans^arr[i];  // this is bitwise operator .its call XOR  it's return only unique value..  

    }

    return ans;
}

void print_array(int arr[], int size){
    
    for(int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);  // use for fast input and output....

    int arr[5] = {1, 3, 5, 3, 1};

    cout <<"Orginal array: " << endl;
    print_array(arr, 5);
    int result = find_unique(arr, 5);
    cout << result << endl;

    return 0;
}

Find unique numbers in array

10 Answers10

Linked