Cards In Ninja Land.

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
9 upvotes
Asked in company
Visa

Problem statement

You are given an integer array 'CARDS' of size 'N', where 'CARDS[i]' is the number written on the 'ith' card. You are also given an integer ‘GROUPSIZE’, where ‘GROUPSIZE’ is the size of each group.


These cards must be arranged in groups with consecutive numbers written on them.


We must return true if cards can be divided into groups and each card belongs to exactly one group. Else, return false.


For Example : 
Consider ‘N’ = 6, 'CARDS' = [1, 3, 2, 2, 4, 3] and ‘GROUPSIZE’ = 2.

Then, the first and third cards with numbers 1 and 2 can be in one group, the second and fourth cards with numbers 3 and 2 can be in one group and the fifth and the sixth cards with numbers 4 and 3 can be in one group. 

Hence we return true.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two integers ‘N’ and 'GROUPSIZE', representing the number of cards and the size of each group. 

The second line will contains ‘N’ space-separated integers representing array ‘CARDS’.
Output Format : 
Print 'true' if cards can be divided into groups. Else print 'false'.
Note : 
You don’t need to print anything; It has already been handled. Just implement the given function.
Sample Input 1 :
1 1
1
Sample Output 1 :
true
Explanation Of Sample Input 1 :
There is only one card, and it belongs to one group.
Sample Input 2 :
6 2
2 1 3 3 2 2
Sample Output 2 :
true
Constraints :
1 <= N, GROUPSIZE <= 10^5
1 <= CARDS[i] <= N

Time limit: 1 sec
Hint

We can count the integer written on cards in a hash map.

Approaches (1)
Greedy Approach

Approach

  • Make a hashmap ‘countMap’, to count the frequency of each card in the deck.
  • Sort the deck of cards in ascending order.
  • Iterate through the deck, saying the following for each card:
    • If the current card's frequency is 0, proceed to the next card.
    • Else, starting with the current card ‘x’, for each number in a group of size ‘GROUPSIZE’:
      • If the frequency of the number is less than ‘countMap[x]’, return false since the desired group cannot be formed.
      • Decrease the number's frequency in the countMap by ‘countMap[x]’.
  • Return true if we have successfully established all groups.

 

Here is the algorithm :

 

  • Initialize an empty Hash Map ‘countMap’.
  • Sort the ‘CARDS’ array in ascending order.
  • For each integer ‘CARD’ in ‘CARDS’:
    • if ‘countMap[CARD]’ equals 0:
      • continue
    • For each integer ‘x’ from ‘CARD’+'GROUPSIZE'-1 to ‘CARD’:
      • if ‘countMap[x]’<‘countMap[CARD]’:
        • Return false
      • Else:
        • Subtract ‘countMap[CARD]’ from ‘countMap[x]’.
  • Return true.
Time Complexity

O(N*LogN), where 'N' is the number of cards.


We sort the ‘CARDS’ array before iterating, which requires O(N*LogN) time. As we loop through each card once, the succeeding iterations need O(N) time.

 

Hence the overall time complexity will be O(N*LogN).

Space Complexity

O(N), where 'N' is the number of cards.


Extra space is used by the hash map, to store the frequency of each element in ‘CARDS’ array.
 

Hence the overall time complexity will be O(N).

Code Solution
(100% EXP penalty)
Cards In Ninja Land.
Full screen
Console