We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Sales by Match
  2. Discussions

Sales by Match

  • f_klaudia
     + 0 comments

    My 3 Python solutions - two O(n) and one O(n^2)

    # O(n^2)
def sockMerchant(n, ar):
    cnt = 0
    seen = set()
    for num in ar:
        if num not in seen:
            seen.add(num)
            cnt += ar.count(num) // 2
    
    return cnt


# O(n)
def sockMerchant(n, ar):
    ar.sort()
    idx = 0
    cnt = 0
    while idx < len(ar) - 1:
        if ar[idx] == ar[idx + 1]:
            cnt += 1
            idx += 2
        else:
            idx += 1
    return cnt


# O(n)
def sockMerchant(n, ar):
    cnt = [0] * (max(ar) + 1)
    for num in ar:
        cnt[num] += 1
    return sum([num // 2 for num in cnt])