It’s a humble request to @admin that Please at Atleast add one edge case in sample inputs because simple test cases are not that informative about the question
cause currently I am giving starters 38 div 4 and, the problem “Good Pairs” have test cases for which I have coded the solution and it’s still giving wrong answer and I am not able to guess any edge case till now
if it is possible to add edge cases to questions It would be beneficial
I really appreciate any help you can provide. @admin
Thanks and regards
@iamtheone_kool
I am not sure what edge cases in this problem that you are asking the @admin about. Nonetheless, the following is my C++ map-based solution of this problem that does not include any special cases for the input data.
Sure. Let us use base-0 array indexing, and rewrite the third constraint so that both equations have index i in the left-side of the equation. It is required to count the number of ordered pairs (i,j) such that 0 \le i < j \le N-1 such that A_i = B_j and B_i = A_j. There are \frac{N(N-1)}{2} ordered pairs that satisfy the index condition only. Suppose that a map is generated for the array A and B such that the keys in this map are the distinct pairs (A_i,B_i) and the value associated with each key is the ordered vector of indices at which this distinct key occurs in A and B. It is simple to prove that the answer to the problem should be equal to the summation of the count of indices associated with key (A_j,B_j) = (B_i,A_i) for all 0 \leq i \leq N-2 and j > i. This count for a given value i can be computed by applying the STL C++ function std::upper_bound to the map value associated with key (B_i,A_i) as shown in the accepted code.
1 Like
@iamtheone_kool With pleasure. The following is another possible implementation
which stores the count of previous distinct (A_i,B_i) pairs instead of storing their indices.