Russian Dolls (Intuit India)
Updated
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[]) → intExamples
Example 1
sizes = [2, 2, 3, 3]return = 2In 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 = 2Oleg 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^51 ≤ size of doll ≤ 10^5
More Intuit interview questions
- Number of IslandsONSITE INTERVIEW · Seen Nov 2026
- VIP and Regular Service SchedulerPHONE SCREEN · Seen Nov 2026
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Shortest Path from an Encoded GraphOA · Seen Sep 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
Similar questions at other companies
- Minimum Operations to Reduce a Transaction LedgerVisa · OAVisa interview questions
- Maximum Distinct Values After SwapsAkuna Capital · OAAkuna Capital interview questions
- Min OperationAmazon · OA
- Min Cost to Complete All ProjectsSalesforce · OASalesforce interview questions
- Freelancing PlatformJP Morgan Chase · OAJP Morgan Chase interview questions
- Minimum Substrings Without Repeating CharactersMicrosoft · OAMicrosoft interview questions
- Find Length of Longest Good SubsequenceWalmart · OAWalmart interview questions
- Maximum Distinct Values After Cross-Array SwapsScale AI · OAScale AI interview questions
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Task Scheduler with CooldownGoDaddy · OA