- Practice
- Algorithms
- Greedy
- Beautiful Pairs
- Discussions
Beautiful Pairs
Beautiful Pairs
gswheeler + 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.SnoopDizzle + 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.
xor0110 + 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.
Shailjakant + 0 comments for me also
jbhatt1 + 0 comments Agreed, the "disjoint pair" discription is very confusing. I would recommed include an example right in the discription.
wryan42675 + 0 comments Thank you for that!!! I was having trouble understanding the problem. I agree with you 100%, phrasing, very confusing.
rigobrinkman + 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.
mike_buttery + 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)
sarathy_v_krish1 + 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; }
count_coder + 1 comment Hi buddy, can you explain about the last return statement?
shawnxhuang + 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.
md_altafhussain1 + 0 comments Thanks bro your this comment helped me getting 100% score
Akashganga + 1 comment I am still not getting pair-1 return statement
md_altafhussain1 + 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
pro_noobmaster + 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
CodeCody + 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.
michal_lihocky + 3 comments [deleted]CodeCody + 1 comment read my comment below
CodeCody + 4 comments michal_lihocky + 0 comments [deleted]codeharrier + 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.
shuhua_gao + 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
shuhua_gao + 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
CodeCody + 0 comments Yes, good implementation.
SnoopDizzle + 1 comment Your solution is good but there is a simpler O(nlogn) solution that does not need a map.
RobertsN + 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
dalaliarif117 + 0 comments send the code
rahulshetty96 + 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)**
rajeev11430 + 3 comments Posting a solution in a comment section is not a good idea
rahulshetty96 + 1 comment yaha mat mara apni..
a7n007 + 0 comments thats what youre doing now.
a7n007 + 0 comments [deleted]a7n007 + 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.
vhhenriquez + 0 comments genius!
pinya + 1 comment Can you please explain , if(sum
sandip40 + 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.
rajatddjsehgal + 0 comments Can you explain the last four lines of your code i got that if(sum
1616410037_CS3a + 0 comments [deleted]manngondaliya + 0 comments int n = i(); what does i() mean?
prabhjyot28 + 0 comments [deleted]
ai2003lian + 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
CodeCody + 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.
ai2003lian + 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?
CodeCody + 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.
ai2003lian + 0 comments ok, I see what you meant. Thanks!
kholwa + 0 comments Thanks a lot bud, their language is so confusing :(
adk96r + 0 comments Thanks mate!
nikijain97 + 0 comments But I would get (0,0),(1,1),(2,2) in the original case only, giving me 3 without change
ramsrib + 0 comments Thanks CodeCody, this was super helpful to solve the case 4 & case 5.
CDevilCode + 0 comments Thanx Bro, I skipped that line in problem statement :P
jubalissimo + 0 comments you are right thanks
utsav_krishnan + 0 comments Huh,You saved me."Know that the optimal amount of beautiful pairs does not always mean the maximum amount"
jeelvashnav1999 + 0 comments thx bro +1
imhktc + 0 comments I re-read the question after reading your comment, Thanks!
sanujkul + 0 comments Thanks, I didn't read carefully that we must change one int in B but this advice helped!
wryan42675 + 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.
Tmlewallen + 0 comments Wow, you're right, very good catch. That's dumb.
pan3688 + 0 comments thanks, this hint helps! :)
viigihabe + 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.
vovohelo + 0 comments Thank you! I was too frustrated with that cases!
nileshtiwari + 0 comments This was what I missed. Thank you for suggestion.
prabhjyot28 + 0 comments Thanks buddy! you just saved my time.
aurigaKG + 0 comments thanks , that helped :)
akaharvey + 0 comments I curse the problem setter from the bottom of my heart. Very pathetic language and logic is used to form this question.
RodneyShag + 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.
gargakash0306 + 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?
RodneyShag + 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.
gargakash0306 + 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.
nirmalchandhar + 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
kostyanych + 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.
RodneyShag + 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.
neel_flash07 + 0 comments Thanks mate! It really helped in understanding the approach to the problem!
adheep_shetty + 0 comments [deleted]parasmyname + 0 comments Just Awsome
massahud + 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
SnoopDizzle + 0 comments Nice! The author should consider updating the editorial.
xor0110 + 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.
KeyurPotdar + 0 comments [deleted]
harshnigm + 1 comment i've done many questions marked moderate on hackerrank which are easier than this.
dyesdyes + 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).
reubenayres + 0 comments [deleted]
dr0opy + 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; }
hacker98 + 1 comment can u please tell the logic used here?
dr0opy + 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.
prajwalx + 0 comments [deleted]cindy_pm + 1 comment why c+=(min(a[i],b[i])) ?
Himanshu98 + 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.
gargakash0306 + 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?
aesthetic_boy + 0 comments can u please tell me the use of line c-1 in which case?
pulkitgarg33 + 0 comments nice approach bro !
vivek_831 + 0 comments beautiful...........
pg4409 + 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?
pariharyash6 + 0 comments their should be more sample examples for better understandibility
yang_4978 + 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
rushil231100 + 0 comments can you explain the logic?
rajr97555 + 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)
Sort 119 Discussions, By:
Please Login in order to post a comment