Start learning free

LESSON 234 OF 667 · SETS

Guest Check-In in C++: Counting Missing Guests with a Set

Practice Read the full explanation

You get two vectors of names, invited and arrived. Return how many invited guests haven't arrived yet.

A guest may check in more than once. They still count as one guest.

Someone who wasn't invited may check in too. They don't change the answer.

 

Example 1:

Input: invited = ["Ava", "Leo", "Mia", "Zoe"], arrived = ["Leo", "Zoe"]
Output: 2
Explanation: Leo and Zoe are here.
Ava and Mia haven't arrived yet.

Example 2:

Input: invited = ["Ava", "Leo"], arrived = ["Leo", "Max", "Leo"]
Output: 1
Explanation: Leo checked in twice, but he is one guest.
Max wasn't invited.
Only Ava is missing.

Example 3:

Input: invited = ["Sam", "Kim"], arrived = []
Output: 2
Explanation: Nobody has arrived yet.

 

Constraints:

  • invited has 1 to 100 names.
  • arrived has 0 to 100 names.
  • The names in invited are all different.
  • Each name is one word of English letters, starting with a capital letter.
STEP 1 OF 4
    Ctrl + Enter to check

    C++ · SETS

    Guest Check In in C++, explained

    Problem overview

    The function guestsMissing gets two vectors of names, invited and arrived, and returns how many invited guests haven't arrived. A guest may check in more than once and still counts as one guest. Someone who wasn't invited may also check in, and that doesn't change the answer. The names in invited are all different.

    With invited = {"Ava", "Leo", "Mia", "Zoe"} and arrived = {"Leo", "Zoe"} the answer is 2: Ava and Mia are still missing. With invited = {"Ava", "Leo"} and arrived = {"Leo", "Max", "Leo"} the answer is 1. Leo checked in twice, Max wasn't invited, and only Ava is missing. With nobody arrived, the answer is the number of invited guests.

    Approach

    Start by assuming everyone is missing, then take each arrival off the list. Whatever is left at the end is the answer. A set is a good list for this because removing a name from it is simple and safe:

    • if the name is in the set, erase removes it;
    • if the name isn't there, because the guest checked in a second time or was never invited, erase removes nothing and returns 0.

    So the two awkward cases, repeated check-ins and uninvited guests, need no if at all.

    Trace the second example. The set starts as Ava and Leo. The arrival Leo is erased, so the set holds Ava. The arrival Max isn't in the set, so nothing happens. The second Leo isn't in the set any more, so again nothing happens. One name is left, so the function returns 1.

    Step by step

    1. Build the set of missing guests from invited.begin() and invited.end(). At the start, everyone is missing.
    2. Loop over the arrivals with a string named name.
    3. Erase the name from missing.
    4. Return the size of missing after the loop.

    The solution in C++

    class Solution {
public:
    int guestsMissing(vector<string>& invited, vector<string>& arrived) {
        unordered_set<string> missing(invited.begin(), invited.end());
        for (string name : arrived) {
            missing.erase(name);
        }
        return missing.size();
    }
};

    Notes on the C++:

    • The constructor with two iterators copies every value of the vector into the set.
    • erase(name) with a value removes by value. It is safe to call for a value that isn't in the set.
    • size() returns an unsigned type, and it converts to the int return type without trouble for at most 100 names.

    Edge cases and common mistakes

    • Counting arrivals instead. Subtracting arrived.size() from invited.size() is wrong: for {"Ava", "Leo"} and {"Leo", "Max", "Leo"} the sizes are 2 and 3, and 2 - 3 is not the right answer, 1. The sizes also count Leo twice and Max, who was never invited.
    • Checking whether the name is in the set first. It works, but the check is extra work: erase already does nothing for a missing name.
    • Nobody arrived. The loop never runs and the answer is the full size of the set, 2 for {"Sam", "Kim"}.
    • Case. Names compare exactly, so "leo" and "Leo" would be different guests. The names here all start with a capital letter.

    Testing

    • invited = {"Ava", "Leo", "Mia", "Zoe"}, arrived = {"Leo", "Zoe"} gives 2.
    • invited = {"Ava", "Leo"}, arrived = {"Leo", "Max", "Leo"} gives 1.
    • invited = {"Sam", "Kim"}, arrived = {} gives 2.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free