Count Couples

Easy

0/40

Average time to solve is 15m

Contributed by

5 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

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:

Hint 1

Hint 2

For each node is the first BST, is there a corresponding node in the second BST that it can be paired up with?

Approaches (2)

Approach 1

Approach 2

Brute Force

Approach: We can traverse all the nodes in the first BST, and for each node T in the first BST, we can search if there exists X-T in the second BST. The number of nodes for which the complement exists in the second BST is our answer.

Algorithm:

Initialize ans to 0
Start traversal from the root of the first BST
- If current node is NULL, return
- Else, if value in the current node is T
  - Traverse from root of second BST to search for X-T
  - If it is present, increment ans by 1
- Traverse to the left child
- Traverse to the right child
Return ans

Time Complexity

O(N1 * H2), where N1 is the number of nodes in the first BST, and H2 is the height of the second BST.

We iterate over all the nodes in the first BST, and for each node in the first we search if the complement exists in the second BST. Hence, the overall complexity is O(N1 * H2).

Space Complexity

O(1), as a constant amount of extra space is being used.

(100% EXP penalty)

Count Couples

Console