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.
Loading...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Greedy
  4. Beautiful Pairs
  5. Discussions

Beautiful Pairs

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial

Sort 119 Discussions, By:

votes
  • recency
  • votes

Please Login in order to post a comment

  • gswheeler 4 years ago+ 8 comments

    The way the "disjoint pair" condition was phrased was, to me, very confusing.

    As they explained it; "in order for a beautiful pair to be considered disjoint, its indices cannot appear in any other beautiful pairs". This, to me, meant that any indices with multiple value matches would be excluded from the final set.

    What they MEANT was "each i and j index can only be used once in the result set".

    Maybe if they used fewer mathematical expressions and actually spelled out what they were looking for from us.

    139|
    Permalink
    • SnoopDizzle 3 years ago+ 0 comments

      I used to get annoyed by that but I've learned that it's actually on purpose... if they explained a problem like this in a straightforward way, it would be way too easy. And remember, this is already categorized as an easy problem. In fact, you correctly solved the first piece of the puzzle, which is boiling down the problem to a simpler form. I think this is what the problem setter is looking for. Since some problems like this are not based on more complex algorithms, they want to find another way to get you to think hard and carefully. I do agree though that too many variables and subscripts in the problem statement can be a very cheap source of frustration.

      -16|
      ParentPermalink
    • xor0110 3 years ago+ 0 comments

      It's one more of those problems you just want to forget having read it afterwards... I get it that they have to make it sound a bit more mysterious, but it is just phrased very badly, you get it right not because you really understand, but because you have some a priori knowledge of what they probably mean. Like some of the worst IQ tests like "complete the sequence", which has no logic at all.

      14|
      ParentPermalink
    • Shailjakant 3 years ago+ 0 comments

      for me also

      0|
      ParentPermalink
    • jbhatt1 3 years ago+ 0 comments

      Agreed, the "disjoint pair" discription is very confusing. I would recommed include an example right in the discription.

      1|
      ParentPermalink
    • wryan42675 2 years ago+ 0 comments

      Thank you for that!!! I was having trouble understanding the problem. I agree with you 100%, phrasing, very confusing.

      1|
      ParentPermalink
    • rigobrinkman 1 year ago+ 1 comment

      Keep in mind that you háve learned what pairwise disjoint sets are. The objective of a challenge like this is not just to test, but also to educate.

      1|
      ParentPermalink
      • mike_buttery 5 months ago+ 0 comments

        Learning is a sequential process building upon a framework of explain, example and then try.

        The problem description is not straightforward and actually hinders understaning the route to the solution.

        I have enough problem reading Computer Science proofs as I'm self taught. If half of the solution is deciphering the statement to the problem then maybe the site should be called HackerProblemComprehensionRank. (joke)

        0|
        ParentPermalink
    • sarathy_v_krish1 5 months ago+ 2 comments

      C++ solution :

      int beautifulPairs(vector<int> A, vector<int> B) {
          map<int, int> m1, m2;
          bool flag=false;
          int pairs=0;
          for (int i=0;i<A.size();i++)
              m1[A[i]]++;
          for (int i=0;i<B.size();i++)
              m2[B[i]]++;
      
          map<int, int>::iterator it = m1.begin();
          while(it!=m1.end())
          {
              pairs+=min(it->second, m2[it->first]);
              if (it->second!=m2[it->first])
                  flag=true;
              it++;
          }
          if (flag)   return pairs+1;
          return pairs-1;
      }
      
      -1|
      ParentPermalink
      • count_coder 5 months ago+ 1 comment

        Hi buddy, can you explain about the last return statement?

        0|
        ParentPermalink
        • shawnxhuang 4 months ago+ 1 comment

          Because the quesyion was weird asked: you mus change 1 element from B. So in the case A is the same as B, we need minus 1 from the pairs.

          1|
          ParentPermalink
          • md_altafhussain1 3 months ago+ 0 comments

            Thanks bro your this comment helped me getting 100% score

            0|
            ParentPermalink
      • Akashganga 3 months ago+ 1 comment

        I am still not getting pair-1 return statement

        0|
        ParentPermalink
        • md_altafhussain1 3 months ago+ 0 comments

          Question says you have to make exactly one change even if you are getting best possible solution without changing it.

          So in case you are getting best possible solution without changing anything you have to make one change.So your ans becomes bestPossibleAns-1

          0|
          ParentPermalink
    • pro_noobmaster 3 months ago+ 0 comments

      Python Oneliner Code

      def beautifulPairs(A, B):
          return len(A)-sum((Counter(A)-Counter(B)).values())+1 if sum((Counter(A)-Counter(B)).values()) else len(A)-1
      

      Better Code

      def beautifulPairs(A, B):
          diff = sum((Counter(A) - Counter(B)).values())
          return len(A) - diff +1 if diff else len(A) - 1
      
      0|
      ParentPermalink
  • CodeCody 4 years ago+ 15 comments

    If anyone gets caught up on test case 4 and 5. Know that the optimal amount of beautiful pairs does not always mean the maximum amount. You have to always change 1 element in B even if you end up with one less pair than if you didn't.

    87|
    Permalink
    • michal_lihocky 4 years ago+ 3 comments
      [deleted]
      -8|
      ParentPermalink
      • CodeCody 4 years ago+ 1 comment

        read my comment below

        0|
        ParentPermalink
        • CodeCody 4 years ago+ 4 comments

          ah screw it https://www.hackerrank.com/challenges/beautiful-pairs/submissions/code/18643001

          0|
          ParentPermalink
          • michal_lihocky 4 years ago+ 0 comments
            [deleted]
            0|
            ParentPermalink
          • codeharrier 4 years ago+ 1 comment

            Using the (no spoilers) template is a good idea. Here's mine, using (no spoilers) instead.

            https://www.hackerrank.com/challenges/beautiful-pairs/submissions/code/19452567

            It looks like this does more looping than yours, but I think internally yours has to do the same things. And looking at both, it's pretty clear we could have used C and made it even cleaner...templates are overkill in this case.

            2|
            ParentPermalink
            • shuhua_gao 4 years ago+ 0 comments

              It seems that your solution is O(n2). We can have O(nlogn) algorithm by using efficient algorithms. The key for one element x in A, we need to perform efficient searching for a matched element in B. Both binary search and hashing can achieve efficient retrival. For example, CodeCody uses a binary search tree to keep the elements in order for fast binary search. And I use a hash table to performance even faster search in most cases. see https://www.hackerrank.com/challenges/beautiful-pairs/submissions/code/20992981

              0|
              ParentPermalink
          • shuhua_gao 4 years ago+ 2 comments

            I guess there is no need to put both A and B into std::map. After all, we have to iterate over one array and perform search in the other array. Therefore, it is sufficient to put only A into a std::map. Besides, I think hash table (std::unordered_map) is a better choice than binary search tree (std::map) since we only need to retrieve an element as fast as possible rather than retrieve a range, etc.

            With the hash table https://www.hackerrank.com/challenges/beautiful-pairs/submissions/code/20992981

            0|
            ParentPermalink
            • CodeCody 4 years ago+ 0 comments

              Yes, good implementation.

              0|
              ParentPermalink
            • SnoopDizzle 3 years ago+ 1 comment

              Your solution is good but there is a simpler O(nlogn) solution that does not need a map.

              0|
              ParentPermalink
              • RobertsN 3 years ago+ 0 comments

                Maybe a bit shorter and sweeter (build map on reading) and a single pass afterwards.

                https://www.hackerrank.com/challenges/beautiful-pairs/submissions/code/31918682

                0|
                ParentPermalink
          • dalaliarif117 12 months ago+ 0 comments

            send the code

            0|
            ParentPermalink
      • rahulshetty96 3 years ago+ 6 comments

        public static void main(String[] args) {

            int n = i();
            int a[] = new int[1001];
            int sum = 0;
            for(int i=1;i<=n;i++)
            a[i()]++;
        
        
            for(int i=1;i<=n;i++)
            {
                int v = i();
                if(a[v]>0)
                {
                    sum++;
                    a[v]--;
                }
            }
        
        
        
            if(sum<n)
                System.out.print(sum+1);
            else
                System.out.print(sum-1); 
        
        }
        
        **Solution O(n)**
        
        5|
        ParentPermalink
        • rajeev11430 3 years ago+ 3 comments

          Posting a solution in a comment section is not a good idea

          8|
          ParentPermalink
          • rahulshetty96 3 years ago+ 1 comment

            yaha mat mara apni..

            4|
            ParentPermalink
            • a7n007 2 years ago+ 0 comments

              thats what youre doing now.

              3|
              ParentPermalink
          • a7n007 2 years ago+ 0 comments
            [deleted]
            -1|
            ParentPermalink
          • a7n007 2 years ago+ 0 comments

            ignore it if you dont want to learn a new technique that you never knew. or if you have done it the same way.

            0|
            ParentPermalink
        • vhhenriquez 3 years ago+ 0 comments

          genius!

          0|
          ParentPermalink
        • pinya 2 years ago+ 1 comment

          Can you please explain , if(sum

          1|
          ParentPermalink
          • sandip40 11 months ago+ 0 comments

            See, if(sum means there are elements in A which are not matched with B. So max you can change only 1 element in B, here you can directly return sum+1.

            And else case(i.e. sum==n), means A==B(all elements in A matching with B). In this case we would have directly returned sum, but contraint on problem says : you must change one element in B( so here we will lose one pair). That's y returning sum-1.

            0|
            ParentPermalink
        • rajatddjsehgal 2 years ago+ 0 comments

          Can you explain the last four lines of your code i got that if(sum

          -1|
          ParentPermalink
        • 1616410037_CS3a 11 months ago+ 0 comments
          [deleted]
          0|
          ParentPermalink
        • manngondaliya 4 months ago+ 0 comments

          int n = i(); what does i() mean?

          0|
          ParentPermalink
      • prabhjyot28 10 months ago+ 0 comments
        [deleted]
        0|
        ParentPermalink
    • ai2003lian 4 years ago+ 1 comment

      caught up on 4 and 5 too. but i don't understand why you said "optimal amount of beautiful pairs does not always mean the maximum amount" it clearly states in the problem that "resulting number of pairwise disjoint beautiful pairs is maximal" after changing 1 number in B

      0|
      ParentPermalink
      • CodeCody 4 years ago+ 1 comment

        I made the mistake of just looking to make the maximum amount pairs. If changing 1 element in B gave me less pairs then I disregarded it. That was my mistake.

        0|
        ParentPermalink
        • ai2003lian 4 years ago+ 1 comment

          A and B have same number of elements, doesn't it mean by changing 1 element in B to whatever value left in A we'll always end up with 1 more beautiful pair?

          0|
          ParentPermalink
          • CodeCody 4 years ago+ 6 comments

            Yes in all cases but 4 and 5, which is a case where A and B have the same number of elements and the same number of each value. In this case changing B results in one less pair.

              ORIGINAL
            A : 1 1 1
            B : 1 1 1
            
              CHANGE
            A : 1 1 1
            B : 1 1 2
            

            In a case like this without changing B, you can get 3 pairs,but since you have to change B, you only get 2.

            10|
            ParentPermalink
            • ai2003lian 4 years ago+ 0 comments

              ok, I see what you meant. Thanks!

              0|
              ParentPermalink
            • kholwa 3 years ago+ 0 comments

              Thanks a lot bud, their language is so confusing :(

              0|
              ParentPermalink
            • adk96r 3 years ago+ 0 comments

              Thanks mate!

              0|
              ParentPermalink
            • nikijain97 2 years ago+ 0 comments

              But I would get (0,0),(1,1),(2,2) in the original case only, giving me 3 without change

              0|
              ParentPermalink
            • ramsrib 2 years ago+ 0 comments

              Thanks CodeCody, this was super helpful to solve the case 4 & case 5.

              0|
              ParentPermalink
            • CDevilCode 5 months ago+ 0 comments

              Thanx Bro, I skipped that line in problem statement :P

              0|
              ParentPermalink
    • jubalissimo 3 years ago+ 0 comments

      you are right thanks

      0|
      ParentPermalink
    • utsav_krishnan 3 years ago+ 0 comments

      Huh,You saved me."Know that the optimal amount of beautiful pairs does not always mean the maximum amount"

      0|
      ParentPermalink
    • jeelvashnav1999 3 years ago+ 0 comments

      thx bro +1

      0|
      ParentPermalink
    • imhktc 2 years ago+ 0 comments

      I re-read the question after reading your comment, Thanks!

      0|
      ParentPermalink
    • sanujkul 2 years ago+ 0 comments

      Thanks, I didn't read carefully that we must change one int in B but this advice helped!

      0|
      ParentPermalink
    • wryan42675 2 years ago+ 0 comments

      Thank You!! Writing the code for this problem is easy, understanding the problem, hard. I'm not convinced the problem description is complete.

      1|
      ParentPermalink
    • Tmlewallen 2 years ago+ 0 comments

      Wow, you're right, very good catch. That's dumb.

      0|
      ParentPermalink
    • pan3688 2 years ago+ 0 comments

      thanks, this hint helps! :)

      0|
      ParentPermalink
    • viigihabe 1 year ago+ 2 comments

      "Your task is to change exactly element in so that the size of the pairwise disjoint beautiful set is maximum." In test case 5 changing one element does exactly opposite! So, if the statement is "to change to increase" it f@¢ing MUST mean increasing not decreasing. Or at least it must be said, if you cannot change for increasing you must change anyway. But its not said. It is said : "change ... so that the size ... is maximum". Ambiguity in wording. Even fifth grader can do better. Had to open both test cases (5 hackos each) to determine that BS. From first opening I still thought that there might be bug in my code. But no, there is bug in challenge wording.

      2|
      ParentPermalink
      • RobertsN 1 year ago+ 0 comments

        Welcome to real world specifications :)

        1|
        ParentPermalink
      • hongze_x 10 months ago+ 0 comments

        Thanks for saving me 5 hackos. The problem statement is poorly written.

        0|
        ParentPermalink
    • vovohelo 1 year ago+ 0 comments

      Thank you! I was too frustrated with that cases!

      0|
      ParentPermalink
    • nileshtiwari 1 year ago+ 0 comments

      This was what I missed. Thank you for suggestion.

      0|
      ParentPermalink
    • prabhjyot28 10 months ago+ 0 comments

      Thanks buddy! you just saved my time.

      0|
      ParentPermalink
    • aurigaKG 8 months ago+ 0 comments

      thanks , that helped :)

      0|
      ParentPermalink
  • akaharvey 3 years ago+ 0 comments

    I curse the problem setter from the bottom of my heart. Very pathetic language and logic is used to form this question.

    27|
    Permalink
  • RodneyShag 3 years ago+ 5 comments

    Java O(n) solution

    From my HackerRank solutions.

    For an element in A, if there's a matching element in B, this creates a "beautiful pair". Each element can only be used once to create a beautiful pair.

    Additionaly, We MUST change exactly 1 element in B. We attempt to change it to create 1 more beautiful pair. In the special case where we already have the max number of beautiful pairs, being forced to change it gives us 1 less beautiful pair.

    Time Complexity: O(n)
    Space Complexity: O(1)

    import java.util.Scanner;
    
    public class Solution {
        
        private static final int MAX_NUM = 1000;
        
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int N = scan.nextInt();
            int [] bucketA = new int[MAX_NUM + 1];
            for (int i = 0; i < N; i++) {
                bucketA[scan.nextInt()]++;
            }
            int beautifulPairs = 0;
            for (int i = 0; i < N; i++) {
                int num = scan.nextInt();
                if (bucketA[num] > 0) {
                    bucketA[num]--;
                    beautifulPairs++;
                }
            }
            scan.close();
            
            /* Accounts for changing 1 element in B */
            if (beautifulPairs == N) {
                beautifulPairs--;
            } else {
                beautifulPairs++;
            }
            System.out.println(beautifulPairs);
        }
    }
    

    Let me know if you have any questions.

    16|
    Permalink
    • gargakash0306 2 years ago+ 1 comment

      well on analyzing , i got your logic , but will you please tell me for how you thought of making an array which will store 1 at the position of the element and not for an array which will store the values entered?

      0|
      ParentPermalink
      • RodneyShag 2 years ago+ 2 comments

        I'm not sure if I understand your question. I use buckets in this problem. Using buckets to solve a problem is a common trick and I had learned it from various algorithms, so I applied it to this problem.

        HackerRank solutions.

        1|
        ParentPermalink
        • gargakash0306 2 years ago+ 0 comments

          Well thanks for your reply. Now i will try to remember this trick while solving further problems and read about buckets. Thanks buddy.

          1|
          ParentPermalink
        • nirmalchandhar 2 years ago+ 0 comments

          I have been at this hackerrank for about a month now . While this has been a certain learning curve, i am certainly learning a lot from your comments. Real awesome logic

          4|
          ParentPermalink
    • kostyanych 2 years ago+ 1 comment

      Only one question with this approach - how would it work if A and B upper limits would be pushed to, say, 10^12? And N would stay relatively small. Even less than 10. Then your approach would be at least not very economical.

      Of course, the problem as it was defined is solved. But you could have mentioned to the less enlightened that they should think of other ways to compare arrays on account of change in conditions.

      0|
      ParentPermalink
      • RodneyShag 2 years ago+ 0 comments

        Yes, that's a good point, but it's a different problem. If A or B had maxes of 10^12, the runtimes would remain the same since there is an upper limit.

        HackerRank solutions.

        1|
        ParentPermalink
    • neel_flash07 2 years ago+ 0 comments

      Thanks mate! It really helped in understanding the approach to the problem!

      1|
      ParentPermalink
    • adheep_shetty 1 year ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • parasmyname 4 months ago+ 0 comments

      Just Awsome

      0|
      ParentPermalink
  • massahud 3 years ago+ 3 comments

    With a little more thinking got an O(n) solution, since the max possible number is only 1000. https://www.hackerrank.com/challenges/beautiful-pairs/submissions/code/23334407

    Edit: improved version https://www.hackerrank.com/challenges/beautiful-pairs/submissions/code/23342269

    6|
    Permalink
    • SnoopDizzle 3 years ago+ 0 comments

      Nice! The author should consider updating the editorial.

      0|
      ParentPermalink
    • xor0110 3 years ago+ 0 comments

      Sure, and it could be a more generic map instead of an array... It's another way to represent multisets when you don't have to actually keep the different equivalent objects.

      0|
      ParentPermalink
    • KeyurPotdar 3 years ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
  • harshnigm 4 years ago+ 1 comment

    i've done many questions marked moderate on hackerrank which are easier than this.

    6|
    Permalink
    • dyesdyes 3 years ago+ 1 comment

      I finished this in 15 minutes with a dictionary solution. Not sure what you find difficult (although the disjoint pair thingy was a bit confusing at first).

      -12|
      ParentPermalink
      • reubenayres 3 years ago+ 0 comments
        [deleted]
        0|
        ParentPermalink
  • dr0opy 3 years ago+ 7 comments

    here my solutions

    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    
    int main() {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
        int a[1003]={0};
        int b[1003]={0};
        int n,x;
        cin>>n;
        int a1[n],b1[n];
        for(int i=0;i<n;i++){
            cin>>x;
            a[x]++;
        }
        for(int i=0;i<n;i++){
            cin>>x;
            b[x]++;
        }
        int c=0;
        for(int i=0;i<1002;i++){
            if(a[i]>0&&b[i]>0){
                c+=(min(a[i],b[i]));
            }
        }
        if(c<n){
            cout<<c+1<<endl;
        }
        else {
            cout<<c-1<<endl;
        }
        return 0;
    }
    
    5|
    Permalink
    • hacker98 3 years ago+ 1 comment

      can u please tell the logic used here?

      -1|
      ParentPermalink
      • dr0opy 3 years ago+ 2 comments

        Here to count the maximum possible number of pairwise disjoint beautiful pairs we store the frequecy of numbers which are matching in both array A and B.and we can add 1 extra to result as we can change one of the values in b.

        Note:Here for last statement you have to look for the edge case if all the numbers of A matches with array B.then the total count will be (n-1)or (c-1)as its mandatory to change a number in a array.

        1|
        ParentPermalink
        • prajwalx 3 years ago+ 0 comments
          [deleted]
          0|
          ParentPermalink
        • cindy_pm 2 years ago+ 1 comment

          why c+=(min(a[i],b[i])) ?

          0|
          ParentPermalink
          • Himanshu98 2 years ago+ 0 comments

            in his solution c+=(min(a[i],b[i])), here min is acting as min intersection between corresponding elements in count array, means take out the least probablity of intersection. and add it to variable c. example: suppose after counting we get the following count array. a_count=[1,2,0,2] b_count=[1,2,2,0]

            for, i=0 min is 1, so c=1 i=1 min is 2 then c=1+2=3 i=2 min is 0 so c remains same , and so on.

            0|
            ParentPermalink
    • Deepeka 3 years ago+ 1 comment

      why have you declared a1 and b1

      0|
      ParentPermalink
      • dr0opy 3 years ago+ 0 comments

        Just skip it, it's just declaration

        0|
        ParentPermalink
    • gargakash0306 2 years ago+ 0 comments

      well on analyzing , i got your logic , but will you please tell me for how you thought of making an array which will store 1 at the position of the element and not for an array which will store the values entered?

      0|
      ParentPermalink
    • aesthetic_boy 2 years ago+ 0 comments

      can u please tell me the use of line c-1 in which case?

      0|
      ParentPermalink
    • pulkitgarg33 1 year ago+ 0 comments

      nice approach bro !

      0|
      ParentPermalink
    • vivek_831 6 months ago+ 0 comments

      beautiful...........

      0|
      ParentPermalink
    • pg4409 3 weeks ago+ 0 comments

      hey, I was analysing your logic for the FOR LOOP, but couldn't get it. Say if A = 1,2,3,4 and B = 1,2,3,3. Then, after the for loop, c = 7. and finally, we subtract 1 and get 6.??? I know I'm wrong, can you please explain the if condition and the increment in c variable lines?

      0|
      ParentPermalink
  • pariharyash6 3 years ago+ 0 comments

    their should be more sample examples for better understandibility

    4|
    Permalink
  • yang_4978 10 months ago+ 1 comment

    Python 2-liner:

    from collections import Counter
    
    def beautifulPairs(A, B):
        result = sum((Counter(A)&Counter(B)).values())
        return result+1 if(result<len(B)) else result-1
    
    3|
    Permalink
    • rushil231100 5 months ago+ 0 comments

      can you explain the logic?

      0|
      ParentPermalink
  • rajr97555 11 months ago+ 0 comments

    My Code

    N = int(input())
    A = list(map(int, input().split() ))
    B = list(map(int, input().split() ))
    
    ans = 0;
    for i in range(N):
        for j in range(len(B)):
            if A[i] == B[j]:
                B.pop(j)
                ans += 1
                break
    if ans == N:
        ans -= 1
    else:
        ans += 1
    print(ans)
    
    3|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature