HackerRank - 30 Days of Code - Day 1

Problem: Sales by Match

There is a large pile of socks that must be paired by color. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

For example, there are n = 7 socks with colors ar = [1,2,1,2,1,3,2]. There is one pair of color 1 and one of color 2. There are three odd socks left, one of each color. The number of pairs is 2.

Function Description

Complete the sockMerchant function in the editor below. It must return an integer representing the number of matching pairs of socks that are available.

sockMerchant has the following parameter(s):

• n: the number of socks in the pile
• ar: the colors of each sock

Input Format

The first line contains an integer n, the number of socks represented in ar. The second line contains n space-separated integers describing the colors ar[i] of the socks in the pile.

Constraints

• 1 <= n <= 100
• 1 <= ar[i] <= 100 where 0 <= i < n

Output Format

Return the total number of matching pairs of socks that John can sell.

Sample Input

Copycopy code to clipboard
19
210 20 20 10 10 30 50 10 20

Sample Output

Copycopy code to clipboard
13

Explanation

John can match three pairs of socks.

Solution

After thinking about the problem, I came up with the following solution:

• Create a map of the socks
• Iterate over the array of socks
• If the sock is in the map, increment the pairs value by 1 and delete the number in the map
• If the sock is not in the map, add it to the map with a value of 1
• Return the number of pairs

Copycopy code to clipboard
1function sockMerchant(n, ar) {
2  let map = {};
3  let pairs = 0;
4
5  for (let i = 0; i < n; i++) {
6    if (map[ar[i]]) {
7      pairs++;
8      delete map[ar[i]];
9    } else {
10      map[ar[i]] = 1;
11    }
12  }
13
14  return pairs;
15}

Time Complexity

The time complexity of this solution is O(n). We iterate over the array of socks once. We also iterate over the map once, but the map will never have more than 100 items in it, so the time complexity is still O(n).

Reference

• HackerRank - 30 Days of Code - Day 1