Determine duplicates/pairs in an array in C-CodePudding

I have been doing this problem for 2 days now, and I still can't figure out how to do this properly.

In this program, I have to input the number of sticks available (let's say 5). Then, the user will be asked to input the lengths of each stick (space-separated integer). Let's say the lengths of each stick respectively are [4, 4, 3, 3, 4]. Now, I have to determine if there are pairs (2 sticks of same length). In this case, we have 2 (4,4 and 3,3). Since there are 2 pairs, we can create a canvas (a canvas has a total of 2 pairs of sticks as the frame). Now, I don't know exactly how to determine how many "pairs" there are in an array. I would like to ask for your help and guidance. Just note that I am a beginner. I might not understand complex processes. So, if there is a simple (or something that a beginner can understand) way to do it, it would be great. It's just that I don't want to put something in my code that I don't fully comprehend. Thank you!

Attached here is the link to the problem itself. https://codeforces.com/problemset/problem/127/B

Here is my code (without the process that determines the number of pairs)

#include<iostream>
#include<cmath>
#define MAX 100

int lookForPairs(int numberOfSticks);

int main(void){
    int numberOfSticks = 0, maxNumOfFrames = 0;

    std::cin >> numberOfSticks;
    maxNumOfFrames = lookForPairs(numberOfSticks);
    std::cout << maxNumOfFrames << std::endl;
    return 0;
}

int lookForPairs(int numberOfSticks){
    int lengths[MAX], pairs = 0, count = 0, canvas = 0;

    for(int i=0; i<numberOfSticks; i  ){
        std::cin >> lengths[i];
    }
    pairs = floor(count/2);
    canvas = floor(pairs/2);
    return count;
}

I tried doing it like this, but it was flawed. It wouldn't work when there were 3 or more integers of the same number (for ex. [4, 4, 3, 4, 2] or [5. 5. 5. 5. 6]). On the first array, the count would be 6 when it should only be 3 since there are only three 4s.

 for(int i=0; i<numberOfSticks; i  ){
        for (int j=0; j<numberOfSticks; j  ){
            if (lengths[i] == lengths[j] && i!=j)
            count  ;
        }
    }

CodePudding user response：

Instead of storing all the lengths and then comparing them, count how many there are of each length directly.

These values are known to be positive and at most 100, so you can use an int[100] array for this as well:

int counts[MAX] = {}; // Initialize array to all zeros.

for(int i = 0; i < numberOfSticks; i  ) {
    int length = 0;
    std::cin >> length;
    counts[length-1]  = 1; // Adjust for zero-based indexing.
}

Then count them:

int pairs = 0;
for(int i = 0; i < MAX; i  ) {
    pairs  = counts[i] / 2;
}

and then you have the answer:

return pairs;

CodePudding user response：

Just an extension to molbdnilo's answer: You can even count all pairs in one single iteration:

for(int i = 0; i < numberOfSticks;   i)
{
    if(std::cin >> length) // catch invalid input!
    {
        pairs  = flags[length] == 1; // add a pair if there is already a stick
        flags[length] ^= 1;          // toggle between 0 and 1...
    }
    else
    {
        // some appropriate error handling
    }
}

Note that I skipped subtracting 1 from the length – which requires the array being one larger in length (but now it can be of smallest type available, i.e. char), while index 0 just serves as an unused sentinel. This variant would even allow to use bitmaps for storing the flags, though questionable if, with a maximum length that small, all this bit fiddling would be worth it…

CodePudding user response：

You can count the number of occurrences using a map. It seems that you are not allowed to use a standard map. Since the size of a stick is limited to 100, according to the link you provided, you can use an array, m of 101 items (stick's minimum size is 1, maximum size is 100). The element index is the size of the stick. The element value is the number of sticks. That is, m[a[i]] is the number of sticks of size a[i]. Demo.

#define MAX 100

int n = 7;
int a[MAX] = { 1,2,3,4,1,2,3 };

int m[MAX   1]; // maps stick len to number of sticks

void count()
{
  for (int i = 0; i < n;   i)
    m[a[i]]  ;
}

int main()
{
  count();
  for (int i = 1; i < MAX   1;   i)
    if (m[i])
      std::cout << i << "->" << m[i] << std::endl;
}

CodePudding user response：

Your inner loop is counting forward from the very beginning each time, making you overcount the items in your array. Count forward from i , not zero.

    for(int i=0; i<numberOfSticks; i  )
    {
        for (int j=i; j<numberOfSticks; j  ) { // count forward from i (not zero)
            if (lengths[i] == lengths[j] && i!=j) 
            { // enclosing your blocks in curly braces , even if only one line, is easier to read
                count  ; // you'll want to store this value somewhere along with the 'length'. perhaps a map?
            } 
        }
    }