Counter in arrays c++

Question

i have a really simple code right there that counts how much values you need in arrays.

for (int i = 0; i < dm; i++)
    {
        if (arr[i] == c)
        {
            counter++;
        }
    };

But i need to make it a little bit tricky.I need to count number of same values. Imagine i have an array {4,4,4,3,3,2,2,1,1,0,0,0} and i need to find how much "twins" there. So 3,2,1 are twins because they have only 1 exact friend. I tried something like 2 fors and 2 counters but still have troubles. Thanks. Hope you understand what i mean by "twin". x and x are twins and y,y,y are not ( just in case)

Answer 1

You can do that in one pass and use binary search for efficiency:

int arr[] = { 4,4,4,3,3,2,2,1,1,0,0,0 };
int twins = 0;
for( auto i = std::begin( arr ); i != std::end( arr ); ) {
    auto next = std::upper_bound( i, std::end( arr ), *i, std::greater<int>() );
    if( std::distance( i, next ) == 2 ) ++twins;
    i = next;
}       

Live example

In case there are not too many duplicates in the array std::upper_bound could be not efficient and can be easily replaced:

    auto next = std::find_if( std::next( i ), std::end( arr ), [i]( int n ) { return *i != n; } );

Answer 2

Solution without using additional array:

int twins_counter = 0;
for (int i = 0; i < dm; i++)
{
    int counter = 0; // counter for elements 
    for (int j = 0; j < dm; j++)
    {
        if (arr[i] == arr[j])
        {
            if( j < i )
            {
                 break; // we have searched twin for this element already
            }
            counter++;
            if( counter > 2 )
            {
                break; // we meet element third time, it isn't twin
            }
        }
    }

    if( counter == 2 )
    {
          twins_counter++;
     }
};

For sorted (upwards or downwards) arrays one cycle is enough:

int twins_counter = 0;
int counter = 1;

for (int i = 1; i < dm; i++)
{
    if( arr[i] == arr[i-1] )
    {
         counter++;
     }
     else
     {
           if( counter == 2 )
           {
                 twins_counter++;
                 counter = 1;
           }
     }
}

// check last value
if( counter == 2 )
{
    twins_counter++;
}

Answer 3

I'd make a map that counts - for each individual number in the array - their occurrences. The code could look as follows:

#include <iostream>
#include <map>

int main()
{
    const int numberOfElements = 12;

    int array[numberOfElements] = { 4,4,4,3,3,2,2,1,1,0,0,0 };
    std::map<int,int> counts;
    for (int i=0; i < numberOfElements; i++) {
        counts[array[i]]++;
    }
    for (auto x : counts) {
        if (x.second == 2) {
            cout << "pair: " << x.first << endl;
        }
    }
    return 0;
}

If - for some reason - the range of the elements is limited, you could also use a "plain" array for counting the occurrences. If, for example, the elements are in the range of 0..4, you could use the following fragment:

const int numberOfElements = 12;
const int elementMax = 4;

int array[numberOfElements] = { 4,4,4,3,3,2,2,1,1,0,0,0 };
int counts[elementMax+1] = {};
for (int i=0; i<numberOfElements; i++) {
    counts[array[i]]++;
}
for (int i=0; i <= elementMax; i++) {
    if (counts[i] == 2) {
        cout << "pair: " << i << endl;
    }
}

And if your array is sorted, than a solution without a counter-array could look as follows:

const int numberOfElements = 12;

int array[numberOfElements] = { 4,4,4,3,3,2,2,1,1,0,0,0 };
int prev = -1;
int count = 0;
for (int i=0; i<numberOfElements; i++) {
    if (array[i] == prev) {
      count++;
    }
    else {
        if (count == 2) {
            cout << "pair: " << prev << endl;
        }
        count=1;
        prev = array[i];
    }
}
if (prev >= 0 && count==2) {
    cout << "pair: " << prev << endl;
}