Russian dolls - Find the minimum dolls left

userXDld 0
Viewed 76

I have N dolls of various sizes.

I can put the smaller dolls inside the larger ones, but dolls of the exact same size cannot be placed inside each other.

I have to find the minimum number of dolls that remain when the maximum number of dolls have been packed.

Constraints
1≤N≤ 105
1 ≤ size of doll ≤ 105

Output Print the minimum number of dolls after placing all smaller dolls inside the larger dolls.

Example #1

Input 2, 2, 3, 3
Output 2

Explanation:

  • Put the doll at index 1 inside the doll at index 3 i.e. the doll of size two into the doll size three.
  • Put a doll at index 2 inside the doll at index 4 i.e. doll of size two in size three

We are left with two dolls of size three, which cannot be further placed inside each other. So, the output is 2.

Example #2

Input 1, 2, 2, 3, 4, 5
Output 2

Explanation: We can place dolls at index (1, 2, 4, 5) in the doll at index 6.
So, we will remain with two dolls of sizes two and five.

This is my code:

public int process(List<Integer> doll) {
    Map<Integer, Integer> map = new TreeMap<>();
    for(int key : doll) map.put(key, map.getOrDefault(key,0)+1);
    
    List<Integer> list = new ArrayList<>(map.keySet());
    int maxKey = list.get(list.size()-1);
    int m = map.get(maxKey);
    int result = 0;
    for(int k : map.keySet()) {
        if(k != maxKey) {
            int p = map.get(k);
            if(p > m){
                result += p - m;
            }
        }
    }
    result += m;
    return result;
}

Out of 7 test cases, 3 were failing, and they are HIDDEN test cases so I am not able to see those cases.

How to fix this problem?

java list algorithm
1 Answers

I can put the smaller dolls inside the larger ones, but dolls of the exact same size cannot be placed inside each other.

Basically you need to find the most frequent size of the dolls, it would be equal to the number of remaining dolls.

Because only duplicated sizes impose limitation on how many dolls would leave after placing dolls of smaller sizes into larger dolls.

Let's consider the following example with 16 dolls of sizes from 1 to 5:

   ---   SIZES   --- 
+----------------------+
|  1   2   3   4   5   | -> doll of size 5 containing [4, 3, 2, 1]
|      2   3   4   5   | -> doll of size 5 containing [4, 3, 2]
|      2   3   4   5   | -> doll of size 5 containing [4, 3, 2]
|          3   4       | -> doll of size 4 containing [3]
|          3           | -> empty doll of size 3
+----------------------+

After folding the data by placing all smaller dolls into large dolls, we would have 5 dolls:

  • 3 dolls of size 5;
  • 1 doll of size 4;
  • 1 doll of size 3;

The total number of dolls is bounded by the most frequent size.

public static int process(List<Integer> doll) {
    Map<Integer, Integer> sizeByCount = new HashMap<>();
    
    for (int size : doll) {
        sizeByCount.merge(size, 1, Integer::sum); // or sizeByCount.put(size, sizeByCount.getOrDefault(size, 0) + 1);
    }
    
    int max = 0;
    
    for (int count : sizeByCount.values()) {
        max = Math.max(count, max);
    }
    
    return max;
}

In case if you're comfortable with Streams API, this code can be replaced with a single statement:

return doll.stream()
    .collect(Collectors.toMap(Function.identity(), e -> 1, Integer::sum))
    .values().stream()
    .max(Comparator.naturalOrder())
    .orElse(0);

main()

public static void main(String[] args) {
    System.out.println(process(List.of(1, 2, 2, 3, 4, 5)));
    System.out.println(process(List.of(2, 2, 3, 3)));
}

Output:

2
2
Alexander Ivanchenko0
Related