FastPrep
Problem · Hash Table

Russian Dolls (Intuit India)

Learn this problem
● EasyIntuit logoIntuitINTERNOA

Problem statement

Oleg has N dolls of various sizes. He can place the smaller dolls inside the larger ones, but dolls of the exact same size cannot be placed inside each other. He needs to find the minimum number of dolls that remain when the maximum number of dolls have been packed.

Input

The first line of input contains an integer N representing the number of dolls initially. The second line consists of N space-separated integers representing the size of dolls.

Output

Print an integer representing the minimum number of dolls Oleg has after placing all smaller dolls inside the larger dolls.

Function

minimumNumberOfDolls(sizes: int[]) → int

Examples

Example 1

sizes = [2, 2, 3, 3]return = 2

In order to be left with the minimum number of dolls, Oleg will do the following:

  • Puts doll at index 1 inside doll at index 3 i.e doll of size two in size three.
  • Puts doll at index 2 inside box at index 4 i.e doll of size two in size three.
Now he is left with two dolls of size three which cannot be further placed inside each other. So, the output is 2.

Example 2

sizes = [1, 2, 2, 3, 4, 5]return = 2

Oleg will place dolls at index (1, 2, 4, 5) in the doll at index 6. So, he will remain with two dolls of sizes two and five.

Constraints

1 ≤ N ≤ 10^5
1 ≤ size of doll ≤ 10^5

More Intuit problems

drafts saved locally
public int minimumNumberOfDolls(int[] sizes) {
    // write your code here
}
sizes[2, 2, 3, 3]
expected2
checking account