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. Prepare
  2. Algorithms
  3. Greedy
  4. Beautiful Pairs
  5. Discussions

Beautiful Pairs

Sort by

recency

|

287 Discussions

|

  • alban_tyrex
     + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/coANgIdBKAk

    int beautifulPairs(vector<int> A, vector<int> B) {
    map<int, int> mp;
    int result = 0;
    for(int i = 0; i < A.size(); i++) mp[A[i]]++;
    for(int i = 0; i < B.size(); i++){
        if(mp[B[i]]){
            mp[B[i]]--;
            result++;
        }
    }
    return (result == A.size()) ? result - 1 : result + 1;
}

  • pub_ashishk28
     + 0 comments

    Exhaustively, this problem can be considered in two cases

    1. A and B are similar. That is, for each item in A, there exists an item in B and there is no unmatched item in A. This directly implies vice-versa. In this case then, you will have to change something in B to something that's not in A. So you count no of paired items and reduce one.

    2. A and B are not similar. That is, there is at least one item in A that doesn't have its correponding pair in B which also implies vice-versa. In this case, you can change any one of those unmatched items in B back to something that already exists in A. So you count no of paired items and add one.

    Here is python3 solution. I must add this is not a greedy problem at all. A greedy approach requires making optimal choice at each pass of your solution. 

    def beautifulPairs(A, B):
    # Write your code here
    
    freq_A = Counter(A) # build a frequency dictionary
    
    paired = 0
    for i in B:
        if freq_A[i] > 0:
            paired += 1
            freq_A[i] -= 1
            
    common = freq_A.most_common(1)[0] #returns a tuple 
    
    if common[1] > 0:   #at least one unmatched item in A
        return paired + 1
    else:               # A and B are similar
        return paired - 1

  • deekshachauhan21
     + 0 comments

    can anyone help me out with this C# code its failing fro one testcase:

    public static int beautifulPairs(List A, List B) { HashSet setB = new HashSet(B); int bPairs = 0;

    foreach (int i in A)
{
    if (setB.Contains(i))
    {
        bPairs++;
        setB.Remove(i); // Ensures pairwise disjoint condition
    }
}

// If all elements are matched, changing any element reduces the count
if (bPairs == A.Count)
{
    return bPairs - 1; // Change one element in B to break a pair
}
else
{
    return bPairs + 1; // We can increase the count by changing one element in B
}

    }

  • abhayad268207
     + 1 comment

    Solution of Beautiul Pairs

    def beautifulPairs(A, B):
    # Write your code here
    count = 0
    
    if len(A) == 1:
        return count
    
    for i in A:
        if i in B:
            count += 1
            B.remove(i)
            
    if (count < len(A)):
        return count + 1 
    else:
         return len(A) - 1

  • jmcparland
     + 0 comments

    Haskell

    The mandatory "must change a value" was kind of bullshit, but otherwise...

    module Main where

import qualified Data.Map  as M
import qualified Data.Set  as S

dist :: [Int] -> M.Map Int Int
dist xs = M.fromListWith (+) [(x, 1) | x <- xs]

solve :: [Int] -> [Int] -> Int
solve as bs = do
    let sab = S.fromList $ as ++ bs
    let mbase = M.fromList [(x, 0) | x <- S.elems sab]
    let ma = M.unionWith (+) mbase $ dist as
    let mb = M.unionWith (+) mbase $ dist bs
    let naturals = sum $ M.unionWith min ma mb
    let deltas = M.unionWith (-) mb ma
    let nonzeros = M.filter (/= 0) deltas
    let (poss, negs) = M.partition (> 0) nonzeros
    let correction = if null poss || null negs then -1 else 1
    naturals + correction

main :: IO ()
main = do
    _ <- getLine
    as <- map read . words <$> getLine :: IO [Int]
    bs <- map read . words <$> getLine :: IO [Int]
    print $ solve as bs