Kevin And His Cards

Easy
0/40
Average time to solve is 20m
profile
Contributed by
10 upvotes
Asked in companies
AdobeAmazonZS

Problem statement

Kevin has two sorted packs of cards. The first pack has N cards and the second one has M cards. Every card has an integer written on it. Now, you have to tell two things. First, how many different types of cards does Kevin have with both packs(union). Second, how many types both the packs have in common(intersection).

Note : 
Two cards are said to be of different types if they have different numbers written on them.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.

Then the T test cases follow.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the total number of cards in the first and the second pack, respectively.

The second line of each test case contains ‘N’ space-separated, non-decreasing integers representing the numbers written on the cards of the first pack.

The third line of each test case contains ‘M’ space-separated, non-decreasing integers representing the numbers written on the cards of the second pack.
Output format : 
For each test case, the number of different types of cards (including both the packs) and the number of similar cards in both packs is printed.

Both the numbers should be separated by a single space.

The output of each test case is printed in a separate line.
Constraints : 
1 <= T <= 10
1 <= N, M <= 500
-10^9 <= arr[i] <= 10^9

Time Limit: 1 sec
Sample Input 1 :
1
4 2
1 2 3 4
1 2
Sample Output 1 :
4 2
Explanation For Sample Input 1 :
Different types of cards in both the packs: 1, 2, 3, 4.

Types of cards that are common in both packs: 1, 2.
Sample Input 2 :
2
5 3
2 4 6 8 10
1 3 5
4 4
0 0 1 1
0 0 1 1
Sample Output 2 :
8 0
2 4
Hint

Use nested loops to find different and similar cards among both the packs. 

Approaches (2)
Brute Force approach

For different cards, iterate one by one through both the packs and pick only those types of cards that aren’t picked yet.

 

For similar cards, iterate through pack 1 and also iterate through the pack 2 as a nested loop inside the previous loop. If found any card same in both the packs and isn’t picked yet, then pick it.

 

Algorithm: 

 

  • Loop on pack 1
    • Check in previously picked cards (use a hash table for this), if any different type of card is found that isn’t picked yet, pick it.
  • Similarly, pick different types of cards from pack 2.
  • Loop on pack 1
    • Loop on pack 2
      • If any card of pack 1 is the same as of pack 2 and is not picked yet, pick it.
      • Insert the index of this card in the array/hash table which stores previously picked cards.
  • Return the count of different cards and similar cards.
Time Complexity

O(N * M), where N is the total number of cards in pack-1 and M is the total number of cards in pack-2.

 

For different cards: We are simply iterating over the pack-1 and pack-2 which leads to time complexity of O(N + M). Searching and Insertion is constant because we are using a hash table to store the already picked cards.

 

For similar cards: We are visiting all the cards of pack-2 for every card of pack-1, which leads to O(N * M) complexity in the worst case. For searching and insertion, a hash table is used.

 

Total time complexity becomes O(N + M) + O(N * M) + O(1)

Thus, the final time complexity is O(N * M).

Space Complexity

O(N + M), where N is the total number of cards in pack-1 and M is the total number of cards in pack-2.

 

We are using a hash table to store cards of both packs which will store (N + M) cards in the worst case. Thus, the final space complexity is O(N + M).

Code Solution
(100% EXP penalty)
Kevin And His Cards
Full screen
Console