Problem Overview

The Sales By Mach problem on HackerRank is a classic counting problem. You are given a pile of socks, each with a color represented by an integer. The task is to determine how many pairs of socks with matching colors exist.

You are given:

  • An integer n representing the total number of socks.
  • An array of integers representing the color of each sock.

The goal is to count the total number of matching pairs. A pair consists of two socks with the same color.

This problem is excellent for practicing hash maps (dictionaries) or arrays for counting, and it helps build understanding of simple frequency counting techniques.

Problem Difficulty & Tags

The Sales by Match problem is considered Easy on HackerRank. It focuses on basic counting and frequency analysis.

Relevant tags for this problem include:

  • Algorithms
  • Hash Maps / Dictionaries
  • Arrays
  • Counting

Understanding the Problem

At its core, the Sales by Match problem is asking: "Given a collection of socks, how many pairs can you form?"

Breaking it down:

  • Each sock has a color represented by an integer.
  • A pair consists of exactly two socks of the same color.
  • The task is to count the total number of such pairs in the collection.

Key points to consider:

  • If a color appears only once, it cannot form a pair.
  • If a color appears multiple times, the number of pairs is floor(count / 2).
  • All colors are independent; pairs of one color do not affect pairs of another color.

This problem encourages thinking about efficient counting methods, such as using a hash map (dictionary) to store frequencies, which avoids the need for nested loops and ensures the solution is fast even for large numbers of socks.

Approach / Logic Explanation

To solve the Sales by Match problem efficiently, we need to count how many socks of each color exist and then determine how many pairs can be formed. Here’s how I usually approach it:

Step 1: Use a Hash Map / Dictionary

Create a hash map (or dictionary) to store the frequency of each sock color. The keys will be the sock colors, and the values will be the number of socks of that color.

Step 2: Count Frequencies

Iterate through the list of socks and update the count for each color in the map:

  • If the color is not in the map, add it with a count of 1.
  • If it already exists, increment the count by 1.

Step 3: Calculate Pairs

For each color in the map, the number of pairs is calculated as count // 2 (integer division). Sum these values for all colors to get the total number of pairs.

Step 4: Return the Result

Output the total number of pairs. This solution works efficiently because it only requires a single pass through the socks to count frequencies, and another pass through the map to sum pairs.

Using this approach, the time complexity is O(n), and space complexity is also O(n) in the worst case where all socks have unique colors.

Solution Code

Below are the implementations of the Sales by Match problem in Python and Java, using a dictionary/hash map to count frequencies and calculate pairs.

Python Solution


n = int(input())
dic = {}
cnt = 0
li = map(int, input().rstrip().split())

for i in li:
    if i not in dic.keys():
        dic[i] = 1
    else:
        dic[i] += 1

for i in dic.values():
    cnt += int(i / 2)

print(cnt)

Java Solution

import java.util.*;

class Result {
    public void findSocksPair(int n, int[] ar) {
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // Initialize map
        for (int i = 0; i < n; i++) {
            map.put(ar[i], 0);
        }

        // Count frequencies
        for (int i = 0; i < n; i++) {
            map.put(ar[i], map.get(ar[i]) + 1);
        }

        // Calculate pairs
        int count = 0;
        for (int i : map.keySet()) {
            count += map.get(i) / 2;
        }

        // Output result
        System.out.println(count);
    }
}

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ar = new int[n + 5];
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            ar[i] = x;
        }

        Result res = new Result();
        res.findSocksPair(n, ar);
    }
}

 

Step-by-Step Walkthrough

Let’s break down how your Sales by Match solution works in Python and Java, step by step.

Step 1: Initialize Data Structures

In Python, we create a dictionary dic to store sock colors and their counts. In Java, we use a HashMap named map for the same purpose.

Step 2: Count Frequencies

Iterate through the list of socks:

  • If the color is not already in the map/dictionary, add it with a count of 1.
  • If it exists, increment its count by 1.

This ensures we know exactly how many socks of each color are present.

Step 3: Calculate Pairs

For each color, the number of pairs is calculated as count // 2 (Python) or count / 2 (Java integer division). Sum these pair counts to get the total number of matching pairs.

Step 4: Output the Result

Print the total number of pairs. In Python, this is simply print(cnt). In Java, we use System.out.println(count) to display the result.

Key Observations

  • The solution works for any number of socks and any distribution of colors.
  • Using a dictionary/hash map ensures O(n) time complexity.
  • Edge cases like all socks being the same color or all unique colors are correctly handled.

Sales by mach

 

Sample Input & Output

Here are some examples to illustrate the input and expected output for the Sales by Match problem:

Input Output Explanation
n = 9
ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]		 3 Pairs formed: (10,10), (10,10), (20,20). Total pairs = 3.
n = 5
ar = [1, 2, 1, 2, 1]		 2 Pairs: (1,1), (2,2). One sock of color 1 remains unmatched.
n = 4
ar = [1, 2, 3, 4]		 0 All socks are unique, no pairs can be formed.

Time & Space Complexity Analysis

Let’s analyze the efficiency of the Sales by Match solution.

Time Complexity

  • We iterate through the list of socks once to count frequencies. Let n be the number of socks.
  • Another iteration is done over the dictionary/hash map values to calculate the number of pairs.
  • Overall, the time complexity is O(n).

Space Complexity

  • We store frequencies of each sock color in a dictionary (Python) or hash map (Java).
  • In the worst case, every sock has a unique color, requiring space for n entries.
  • Therefore, space complexity is O(n).

Summary: This solution is efficient for large inputs because it only traverses the list and map once and uses extra space proportional to the number of unique sock colors.

Mistakes to Avoid & Tips

Warning: Avoid using nested loops to count pairs. This leads to O(n²) time complexity and is inefficient for large inputs.
Common Error: Forgetting to use integer division when calculating pairs. Using normal division may result in incorrect counts.
Pro Tip: Use a dictionary or hash map to count sock frequencies first, then sum the pairs. This ensures O(n) time complexity.
Note: Edge cases such as all socks being unique or all socks of the same color should be tested to ensure correctness.

Related Problems

If you enjoyed solving Sales by Match, here are some similar problems to practice counting and hash map techniques:

Conclusion

The Sales by Match problem is a classic exercise for practicing frequency counting using hash maps or dictionaries. By efficiently counting the occurrences of each sock color, you can easily determine how many matching pairs exist without using nested loops.

From my experience at Solviyo, this problem helps reinforce core concepts like hash map usage, integer division, and efficient iteration. These skills are useful for many algorithmic challenges and coding interviews.

Remember to handle edge cases, such as all socks being unique or all socks being the same color. Testing these cases ensures your solution is robust.

Keep practicing similar counting problems and focus on writing clean, readable code. With each problem you solve, your understanding of algorithms and data structures grows stronger!