FastPrepFastPrep
Problem Brief

Russian Dolls (Intuit India)

INTERNOA

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.

1Example 1

Input
sizes = [2, 2, 3, 3]
Output
2
Explanation

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.

2Example 2

Input
sizes = [1, 2, 2, 3, 4, 5]
Output
2
Explanation

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

Limits and guarantees your solution can rely on.

1 ≤ N ≤ 10^5
1 ≤ size of doll ≤ 10^5
public int minimumNumberOfDolls(int[] sizes) {
    // write your code here
}
Input

sizes

[2, 2, 3, 3]

Output

2

Sign in to submit your solution.