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

Sort by

recency

|

221 Discussions

|

  • 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])

  • michael_chen_0
     + 0 comments

    Python 3 solution:

    def sockMerchant(n: int, ar: list[int]) -> int:
    # return sum(v // 2 for v in collections.Counter(ar).values())
    unpaired, pairs = set(), 0
    for sock in ar:
        if sock in unpaired:
            pairs += 1
            unpaired -= {sock}
            continue
        unpaired |= {sock}
    return pairs

  • outsider973
     + 0 comments

    My rust solution:

    fn sockMerchant(n: i32, ar: &[i32]) -> i32 {
    let odd_socks = ar.iter().fold(HashSet::new(), |mut acc, sock| {
        if acc.remove(sock) == false {
            acc.insert(sock);
        }
        acc
    })
    .len() as i32;
    
    (n - odd_socks) / 2
}

  • vdaons
     + 0 comments

    Python 1 liner: O(N)

    return sum(map(lambda v: v // 2, Counter(ar).values()))

  • mmaffezzoli01
     + 0 comments

    Sort array then loop through to count pairs:

    matches = 0 sortedSocks = sorted(ar)

    if n == 1:
    return 0

i = 0
while i < n - 1:
    if sortedSocks[i] == sortedSocks[i+1]:
        matches += 1
        i += 2
    else:
        i += 1

return matches