Last Updated: 29 Jan, 2021
Kevin And His Cards
Easy
Asked in companies
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.
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
Approaches
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.
- Loop on pack 2
- Return the count of different cards and similar cards.
For different cards: Set two pointers on both of the packs (one on each). Initially, point both the pointers to the first card of their respective packs.
Now, iterate through both the packs simultaneously and after each iteration increment the counter by 1. Whenever you find the same cards in both the packs, increment both the pointers by 1. If cards are different, only increment (by 1) the pointer for which card value is smaller. After this increment both the pointers individually till you find the different types of card in both the pack respectively.
For similar cards: Again, set pointers on both of the packs. Initially, point both the pointers to the first card of their respective packs. This time, increment the counter whenever similar cards are found and then update the pointers according to the card value (Number written on the card).
Algorithm:
- For different cards -
- Pointer1 = 1 and pointer2 = 1
- Loop till pointer1 < size of pack-1 and pointer2 < size of pack-2
- Counter++
- If, pack1[pointer1] = pack2[pointer2] then pointer1++ and pointer2++.
- Else, only increment the pointer by 1 for which card value is smaller.
- Keep incrementing both the pointers by 1 until you find the new (the types which have not been picked yet) different cards. You have to do this individually for both the packs.
- If, pointer1 = size of pack-1 or pointer-2 = size of pack then just break the loop.
- Loop on the remaining cards and increment the counter if found different cards.
- For similar cards -
- Set a new counter. Pointer-1 = 0 and pointer-2 = 0
- Loop till pointer1 < size of pack-1 and pointer2 < size of pack-2
- If cards are the same, counter ++, pointer-1 ++, and pointer-2 ++.
- Otherwise, increment the pointer corresponding which card value is less than the other.
- Return a pair of counters, first denotes different types of cards and the second denotes the similar cards.