Traveller - HackMD

# Traveller Rohit travelled to America. On his return to India, he planned to bring some gadgets. He has **M** gadgets that weigh from **1** to **M**. But when Rohit travels on an aeroplane, he is only allowed to carry a maximum weight of **W**. So, he wants to leave some of the gadgets which are already available in India and bring the maximum number of gadgets that are not available in India. Write a program that reads the **M** gadgets, **W** weight limit and **N** space-separated weights of common gadgets available in India and prints the maximum number of unique gadgets that can be brought into India. --- #### Input The first line of input contains space-separated integers representing the number of gadgets `M`, the maximum weight limit `W`, and number of gadget weights `N`. The second line of input contains `N` space-separated integers representing the weights of common gadgets available in India. --- #### Output The output should be a single line containing an integer representing the maximum number of unique gadgets that can be brought into India. --- #### Explanation **Test Case: 1** If the given `M = 10`, `W = 10`, `N = 3` and `gadget_weights = 1 3 5`. The number of gadgets Rohit wants to bring to India is `10`, which weighs between `1 and 10`, so the gadget weights are `1 2 3 4 5 6 7 8 9 10`. The maximum weight he can carry on an aeroplane is `10`. Gadget weights that are available in India are `1 3 5`. After removing the common gadget weights, the gadget weights are `2 4 6 7 8 9 10`. The possible gadgets that can be brought into India are, * 2, 4 is less than 10 and * 2, 4 and 6 is greater than **10** The maximum number of unique gadgets that can be brought into India is **2**. So the output should be **2**. **Test Case: 2** If the given `M = 14`, `W = 13` `N = 4` and `gadgets = 4 6 8 9`. The number of gadgets Rohit wants to bring to India is `14`, which weighs between `1 and 14`, so the gadget weights are `1 2 3 4 5 6 7 8 9 10 11 12 13 14`. The maximum weight he can carry on an aeroplane is `13`. Gadget weights that are available in India are `4 6 8 9`. After removing the common gadget weights, the gadget weights are `1 2 3 5 7 10 11 12 13 14`. The possible gadgets that can be brought into India are, `1 2 3 5` is less than 13 and `1 2 3 5 7` is greater than **13** The maximum number of unique gadgets that can be brought into India is **4**. So the output should be **4**.