beautiful-pairs.py

"""
Solution to Beautiful Pairs HackerRank challenge.

Challenge: Given two input arrays, A and B, find the maximal number of disjoint pairs (i, j) where A[i] = B[j],
after one element from B is changed. The change can be anything you wish, though it must happen.

Description of Solution:
  - Let Ca[k] = number of occurrences of k in A
  - Let Cb[k] = number of occurrences of k in B
  - for each k in Ca:
      if Ca[k] > Cb[k]:
        increment number of deficits that can be filled by changing an entry in B
      otherwise if Ca[k] < Cb[k]:
        increment the number of excess matches in B that can be converted to match a different k in A
      increment the number of total matches by min(Ca[k], Cb[k])
  - After the main loop, figure out if we have enough excess or unmatched items that we can use to
    fulfill the deficit.
"""
import collections

def find_beautiful(one, two):
    counts_one = collections.defaultdict(int)
    counts_two = collections.defaultdict(int)
    
    for a in one:
        counts_one[a] += 1
    for b in two:
        counts_two[b] += 1
    changes_left = 1
    excess = 0 # extra matches in b that are unnecessary
    deficits = 0 # ones where there aren't enough b's
    matches = 0
    extras = 0
    # find the element that is not matched in a that we can change in b
    for a in counts_one.keys():
        count_one = counts_one[a]
        count_two = counts_two[a]
        if count_two > count_one:
            # if there are extra b's, we can safely remove one of them
            excess += count_two - count_one
        elif count_one > count_two:
            deficits += 1
        matches += min(count_one, count_two)
    for b in counts_two.keys():
        if b not in counts_one:
            extras += 1

    if deficits > 0 and (excess > 0 or extras > 0):
        # can safely convert one of the excess items to fill the deficit
        # or the extra unmatched item to be matched.
        matches += 1
    else:
        # otherwise, the change will result in one of the pairs not being matched
        matches -= 1
    return matches
    
n = int(raw_input())
one = map(int, str(raw_input()).split())
two = map(int, str(raw_input()).split())
print find_beautiful(one, two)