Last Updated: 11 Apr, 2021

Cards In Ninja Land.

Moderate

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 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.

Solve now