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;
}

You may sort you array first, then code to skip checked numbers is easy. — Jarod42
– Jarod42, Commented Mar 30, 2016 at 15:20
I believe I am allowed to sort the array. In this case I would get {0,1,2,4,4,4,5,6,7,7,8,9} but its the skipping the next checked number part that has me stuck — ernie
– ernie, Commented Mar 30, 2016 at 15:25
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 — Garf365
– Garf365, Commented Mar 30, 2016 at 15:26
An other solution is to check with previous numbers (and if present skip it). — Jarod42
– Jarod42, Commented Mar 30, 2016 at 15:27
@ernie To clarify what you are asking; are you asking how many different duplicates are found, or are you asking for how many numbers in total are duplicates? For example: { 1,1,2,2,2,3,3,3 }; The answer to first question would be 3 since there are 3 duplicates, and the 2nd answer would be that there are 8 numbers that are duplicates. — Francis Cugler
– Francis Cugler, Commented Mar 30, 2016 at 17:31

Garf365 · Accepted Answer · 2016-03-30 15:29:55Z

3

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;
}

answered Mar 30, 2016 at 15:29

Garf365

3,7075 gold badges33 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

ernie Over a year ago

Although it is the much, much longer way to do it, this is basically what we are expected to do. I just tried stuff out with the suggestions and basically go this same exact thing. Thank you !

Garf365 Over a year ago

@ernie it's just a naive implementation. Free to you to improve ;) happy that help you

Jonathan Mee Over a year ago

@ernie If this solved your problem don't forget to accept.

DimChtz · Accepted Answer · 2016-03-30 15:29:04Z

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.

Jorn Vernee · Accepted Answer · 2016-03-30 16:07:45Z

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.

karakfa · Accepted Answer · 2016-03-30 15:36:06Z

0

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.

edited Mar 30, 2016 at 15:36

answered Mar 30, 2016 at 15:26

karakfa

67.8k8 gold badges45 silver badges59 bronze badges

Comments

Daniel Langr · Accepted Answer · 2016-03-30 15:36:33Z

0

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;
}

answered Mar 30, 2016 at 15:36

Daniel Langr

24.2k3 gold badges55 silver badges110 bronze badges

2 Comments

Slava Over a year ago

For sorted array you can count duplicates just in one pass without inner loops

Daniel Langr Over a year ago

My solution uses passes over elements only once, i.e., its complexity is O(n), even though with inner loop. Your solution is fine, but it does not distinguish elements being in a sequence 2x, 3x, 4x, ... It depends whether you need to count multiplicities or not.

Nothing More · Accepted Answer · 2016-03-30 15:37:23Z

0

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;
}

answered Mar 30, 2016 at 15:37

Nothing More

9631 gold badge14 silver badges29 bronze badges

1 Comment

Slava Over a year ago

Just use int to remember value and you do not need boolean flag and complex conditions

Luca Davanzo · Accepted Answer · 2016-03-30 15:39:58Z

0

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));
}

edited Mar 30, 2016 at 15:39

answered Mar 30, 2016 at 15:22

Luca Davanzo

21.6k15 gold badges124 silver badges152 bronze badges

3 Comments

Jorn Vernee Over a year ago

"I have to do this using nested for loops and can not use vectors."

Luca Davanzo Over a year ago

map != vectors, btw you're right for "nested loops"

NathanOliver Over a year ago

yes maps are not the same as vectors but normally when someone says they can't use vectors it means it is homework and they typically cannot use any standard containers

Rajeev Singh · Accepted Answer · 2016-03-30 15:45:45Z

0

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;
}

edited Mar 30, 2016 at 15:45

answered Mar 30, 2016 at 15:35

Rajeev Singh

3,3322 gold badges23 silver badges30 bronze badges

Comments

Slava · Accepted Answer · 2016-03-30 16:59:31Z

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;
}

Jonathan Mee · Accepted Answer · 2016-03-30 17:00:16Z

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();

Collectives™ on Stack Overflow

How to find number of duplicates in an array?

10 Answers 10

3 Comments

Comments

Comments

Comments

2 Comments

1 Comment

3 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

10 Answers 10

3 Comments

Comments

Comments

Comments

2 Comments

1 Comment

3 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related