Sock Merchant Problem Solution

You are given an integer array where the integers range from 1 to 100. The goal is to count how many pairs of matching integers you can form.

For example, given the array [3, 1, 3], the matching pair would be the two 3s, so the result would be 1 pair.

To solve this, let's first understand how we can pair integers in the array. An integer can only form a pair if it appears at least twice.

For example:

Input: [3, 1, 3]

• Integer 3 appears twice, forming one pair: (3,3)
• Integer 1 appears once, so it cannot form a pair.

So, the total number of pairs is 1.

Input: [3, 1, 3, 3, 3, 1, 2]

• Integer 3 appears 4 times, resulting in 4 / 2 = 2 pairs.
• Integer 1 appears 2 times, resulting in 2 / 2 = 1 pair.
• Integer 2 appears 1 time, so it results in 1 / 2 = 0 pairs.

Thus, the total number of pairs is 3.

Input: [10, 20, 10, 30, 20, 20, 30, 10]

• Integer 10 appears 3 times, which means it forms 3 / 2 = 1 pair (since 3 divided by 2 is 1).
• Integer 20 appears 3 times, so it also forms 3 / 2 = 1 pair.
• Integer 30 appears 2 times, so it forms 2 / 2 = 1 pair.

Thus, the total number of pairs is 3 (1 pair from 10s, 1 pair from 20s, and 1 pair from 30s).

If an integer appears an odd number of times, integer division handles it correctly.

For example, 1 / 2 = 0 because integer division truncates the result to the nearest integer.

Instead of explicitly forming pairs, we can simplify the task:

1. Count how many times each integer appears in the array.
2. For each integer, divide the count by 2 to get the number of pairs.
3. Sum the total number of pairs.

Here’s an example of implementing the algorithm to solve the problem.

public static int sockMerchant(int n, List<int> list)
{
    // Create an array to store counts of integers (size 101 for integers 1 to 100)
    int[] intCounts = new int[101];
    
    // Count occurrences of each integer in the array
    foreach (int i in list)
    {
        intCounts[i]++;
    }
    
    // Calculate the total number of pairs
    int pairs = 0;
    foreach (int count in intCounts)
    {
        pairs += count / 2;  // Each pair is formed by dividing the count by 2
    }

    return pairs;  // Return the total number of pairs
}

We use an array intCounts of size 101 because the problem guarantees that integers are between 1 and 100. The array stores the count of each integer.

The foreach loop iterates over the input array and increments the corresponding index in intCounts.

The second foreach loop adds up the number of pairs by performing integer division (count / 2) on each frequency.

Since the input integers are limited to a small range (1 to 100), we use an array instead of a more complex data structure like a dictionary. This improves performance by eliminating overhead and making the solution more efficient.