How to find number of duplicates in an array?

Question

I have a given array and I need to determine how to find the number of duplicates in it. I have to do this using nested for loops and can not use vectors. I have tried it so far and I get 3, but the answer should be 2 since only the numbers 4 and 7 repeat. I see why I am getting 3 since it checks 4 two times but I can't seem to figure out how to adjust it so It never checks 4 again once it found a match.

#include <iostream>
using namespace std;

int main() {
    const int num_elements = 12;
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 };

    unsigned int numduplicates = 0;    
    for(int i = 0; i < num_elements; ++i){
        int oneCounterMax = 0;
        for(int j = i + 1; j < num_elements; ++j) {
            if((numbers[i] == numbers[j]) && (oneCounterMax < 1)) {
                ++numduplicates;
                ++oneCounterMax;
            }       

        }
    }       
    cout << numduplicates << endl;
}

Answer 1

Sounds like homework in which case your teacher may be unhappy with this approach even though it doesn't use vector.

Given the input array:

int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 };

You can find the unique size of the array by using a set, because a set:

Is an associative container that contains a sorted set of unique objects of type Key

In C++14 you can build the set like this:

const auto numduplicates = num_elements - set<int>(cbegin(numbers), cend(numbers)).size();

Live Example

In C++11 you can build the set like this:

const auto numduplicates = num_elements - set<int>(numbers, next(numbers, num_elements)).size();

And before that you could build the set like this:

const auto numduplicates = num_elements - set<int>(numbers, numbers + num_elements).size();

Answer 2

Simplest implementation for sorted array:

#include <iostream>
#include <algorithm>

int main()
{
    int numbers[] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 };

    auto b = std::begin( numbers );
    auto e = std::end( numbers );
    std:sort( b, e );
    auto ne = std::unique( b, e );
    std::cout << "duplicates:" << std::distance( ne, e ) << std::endl;
}

or by one loop:

#include <iostream>
#include <algorithm>

int main()
{
    int numbers[] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 };

    auto b = std::begin( numbers );
    auto e = std::end( numbers );
    std:sort( b, e );

    int dups = 0;
    int v = *b++;
    for( auto it = b; it != e; ++it ) {
       if( v != *it ) v = *it;
       else ++dups;
    }
    std::cout << "duplicates:" << dups << std::endl;
}

Answer 3

Most of the answers are good enough, but not striving too far from your solution, there is also a clever trick to be had!:

#include <iostream>
using namespace std;

int main() {
    const int num_elements = 12;
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 };

    unsigned int numduplicates = 0;
    for (int i = 0; i < num_elements; ++i) {
        int counter = 0; // changed name
        for (int j = i + 1; j < num_elements; ++j) {
            if (numbers[i] == numbers[j]) { // changed condition
                ++counter; // only increment counter
            }
        }

        if (counter == 1) { // added if statement
            ++numduplicates;
        }
    }
    cout << numduplicates << endl;
}

Instead of only counting 1 of the duplicates (with oneCounterMax), we count all of them. Then later we check if the number we counted is exactly 1.

This does 2 things:

• We counted at least 1 duplicate, so there is a duplicate of the current number. but...
• If we counted more then 1 duplicate, we don't increment the duplicate counter, because it will already be done later on in our iteration, when we count again for the second to last duplicate.

Answer 4

First you have to sort the array,then skip the repeated elements and increase the value of numduplicates

int main() {
    const int num_elements = 12;
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 };

    sort(numbers,numbers+12);//sorting
    int  numduplicates = 0;
    for(int i = 0; i < num_elements; ++i){
        if((i+1)<num_elements && numbers[i] == numbers[i+1]) {
            ++numduplicates;
            while((i+1)<num_elements && numbers[i] == numbers[i+1])
               i++;
       }       
    }       
    cout << numduplicates << endl;
}

Answer 5

You can use a map, for instance, where key is number[i] and value is occurrences of number[i].

std::map<int,int> m;
std::map<int,int>::iterator it;
for(int i = 0; i < num_elements; ++i) {
   const int key = numbers[i];
   int value = 0;
   it = m.find(key)
   if (it != m.end()) {
      ++value;
   }  
   map.insert(std::make_pair(key,value));
}

Answer 6

First sort the array and then iterate over this sorted array. Use a bool flag to save the current state about whether this number has been counted as a duplicate number.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    const int num_elements = 12;
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 };

    std:sort(numbers, numbers+num_elements);
    int duplicate_count = 0;
    bool duplicate = false;
    for(int i = 1; i < num_elements; i++)
    {
        if(numbers[i] != numbers[i-1])
            duplicate = false;
        else if(numbers[i] == numbers[i-1] && !duplicate)
        {
            duplicate_count++;
            duplicate = true;
        }
    }
    cout << "duplicate count: " << duplicate_count << endl;
    return 0;
}

Answer 7

If you are allowed to sort the array, you can write something like this:

std::sort(numbers, numbers + num_elements);

int k = 0;
while (k < num_elements - 1) {
   int i = 1;
   while ((k + i < num_elements) && (numbers[k + i] == numbers[k])) 
      i++;
   if (i > 1)
      ... // numbers[k] is a duplicate with multiplicity i
   k += i;
}

Answer 8

Once you sort the array, instead of counting duplicates, count the number of transitions where a[i-1] != a[i] && a[i] == a[i+1], which will give the number of duplicate elements. You have to guard for the boundaries though.

Answer 9

You find 3 because you don't check if current number is already count as duplicate : the first 4, you find a duplicate, and the second one also. You have to check if the current number isn't in the begin of array. If it is, it's already count as duplicate, so no need to continue, you can pass to next number

int main() {
    const int num_elements = 12;
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 };


    for(int i = 0; i < num_elements; ++i){
        int oneCounterMax = 0;  
        bool notAlreadyCheck = true;  

        for(int j = 0; j < i-1; ++j) {
            if (numbers[i] == numbers[j]){
                notAlreadyCheck = false;
            }
        }
        if (notAlreadyCheck) {    
            for(int j = i + 1; j < num_elements; ++j) {
                if((numbers[i] == numbers[j]) && (oneCounterMax < 1)) {
                    ++numduplicates;
                    ++oneCounterMax;
                }       
            }
        } 
    }       
    cout << numduplicates << endl;
}

Answer 10

The best way would be to use std::vector and std::map as already mentioned by others. But since you can only use nested loops and arrays here's an example that works:

const int num_elements = 12;
int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 };
int counter = 0;

for ( int i = 0; i < num_elements; i++ ) {
    for ( int j = i + 1; j < num_elements; j++ ) {
        if ( numbers[j] == numbers[i] ) {
            counter++;
            for ( int k = 0; k < i; k++ ) {
                if ( numbers[k] == numbers[j] ) {
                    counter--;
                    break;
                }
            }
            break;
        }
    }
}

cout << counter << endl;

It will print 2 and not 3. Simply, when we find a duplicate, we go back and check if we already met this number.