Problem title
Difficulty
Avg time to solve

Sum of Bit Difference Among all Pairs
Easy
15 mins
Social Networking Graph
Moderate
15 mins
Minimum Cost to Make at Least One Valid Path in a Grid
Moderate
20 mins
Allocate Books
Hard
--
Generate all binary strings from pattern
Moderate
10 mins
Pair Difference K
Moderate
15 mins
Best Time to Buy and Sell Stock III
Hard
10 mins
Russian Doll Envelopes
Hard
50 mins
Insert Interval
Easy
15 mins
Beautiful City
Easy
10 mins
3

Count Couples

Difficulty: EASY
Contributed By
Vishal R S |Level 1
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

There are two groups, one of men, and one of women with unique IDs (Each group has unique IDs but two people from different groups can have the same ID). These two groups are represented in the form of a Binary Search Tree.

Now, the IDs are handed out in such a way that a man and woman are married if and only if their IDs sum up to ‘X’. Given the two groups, find the number of married couples that exist.

Input Format:
The first line contains 'T', denoting the number of test cases.
For each Test :
The first line contains three space separated integers => X, representing the sum, and T1 and T2 representing the number of integers in the next 2 lines.
The second line contains an array A of T1 space separated integers, with a positive integer representing a node and -1 representing  a NULL value.
The third line contains an array B of T2 space separated integers, with a positive integer representing a node and -1 representing  a NULL value.

The input is given is 'Level Order'.
(Note that T1 and T2 are not the number of nodes in the BSTs and N1 = number of positive integers in A and N2 = number of positive integers in B.)
Output Format:
For each test case, print one integer, that is, the number of married couples that exist in the groups.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= T <= 5
1 <= T1,T2 <= 10^5
1 <= A[i] <= 10^9 or A[i] = -1, i ∈ (1,T1)
1 <= B[i] <= 10^9 or B[i] = -1, i ∈ (1,T2)
1 <= X <= 10^9

Note - The sum of 'T1' and ‘T2’ over all test cases do not exceed 2 * 10^5.

Time Limit: 1 sec
Sample Input 1:
1
6 13 11
7 2 9 1 5 -1 14 -1 -1 -1 -1 -1 -1
4 2 5 1 3 -1 -1 -1 -1 -1 -1
Sample Output 1
3
Explanation for Sample Input 1:
The couples for these groups are (1,5), (2,4) and (5,1). Hence, the answer is 3.
Sample Input 2:
1
8 7 7
5 4 7 -1 -1 -1 -1
3 1 4 -1 -1 -1 -1
Sample Output 2:
3
Reset Code
Full screen
copy-code
Console