HackerRank ‘Sock Merchant’ Solution

H
Short Problem Definition:

John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

Link

Sock Merchant

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Group the same color together. Look out for the integer division // that discards the odd socks.

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/bin/python
 
import sys
from collections import defaultdict
 
n = int(raw_input().strip())
c = map(int,raw_input().strip().split(' '))
 
d = defaultdict(int)
for k in c:
    d[k] += 1
     
cnt = 0
for ele in d.values():
    cnt += ele//2
     
print cnt

About the author

Add comment

Archives

Categories