Wardrobe

SRM 308 · 2006-06-24 · by Andrew_Lazarev

SRM 308 · 2006-06-24 · by Andrew_Lazarev · Brute Force, Greedy

Show categories

Class Name: Wardrobe

Return Type: int

Method Name: countUnscrewedHoles

Arg Types: (vector<int>)

Problem Statement

You are attempting to assemble a wardrobe, but you have misplaced the instructions. The wardrobe has several holes, each of which is designed to accommodate a bolt of a specific size. A hole with size D should be matched with a bolt of size D. However, bolts with sizes D-1 and D+1 will also fit. Since you don't have the instructions, you decide to do the following: For each bolt, you will randomly choose an available hole in which the bolt will fit, and screw the bolt into that hole. If the bolt cannot fit into any of the available holes, you will skip it and move on to the next one.

You are given a int[] bolts containing the sizes of the bolts. For each element in bolts, there is a corresponding hole with the same size. Return the maximum number of unused holes that can remain at the end of this process.

Constraints

bolts will contain between 1 and 50 elements, inclusive
Each element of bolts will be between 1 and 100, inclusive.

Examples

{1, 2, 3}
Returns: 1

You can screw the bolt with size 2 into the hole with size 1, and the bolt with size 3 into the hole with size 2. The bolt with size 1 cannot fit into the remaining hole with size 3, so one hole will remain unused in this case.

{1, 2, 3, 2, 4}
Returns: 1

{1, 2, 3, 3, 4, 2, 5, 4}
Returns: 2

{12, 14, 12, 25, 15, 22, 19, 13, 26, 19, 24, 18, 14}
Returns: 2

{26, 26, 26, 14, 13, 28, 27, 15, 27, 28, 28, 26}
Returns: 3

Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Wardrobe with a public method int countUnscrewedHoles(vector<int> bolts) · 118 test cases · 2 s / 256 MB per case