Number of students unable to eat lunch

The school cafeteria offers circular and square sandwiches at lunch break, represented by numbers 0 and 1, respectively. All students stand in a queue, expressing their preference for either square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students, and these sandwiches are placed in a stack. The lunch process unfolds as follows:

• If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
• Otherwise, they will leave the sandwich on the top of the stack and go to the end of the queue.
• This process continues until none of the students in the queue want to take the top sandwich, rendering them unable to eat.

You are given two integer arrays, students and sandwiches, where sandwiches[i] represents the type (0 or 1) of the ith sandwich in the stack, and students[j] represents the preference (0 or 1) of the jth student in the initial queue. Your task is to return the number of students who are unable to eat.

Example 1:

students = [1, 1, 1, 0, 0, 1]
sandwiches = [1, 0, 0, 0, 1, 1]

Output: 3

Example 2:

students = [1, 1, 0, 0]
sandwiches = [0, 1, 0, 1]

Output: 0

Constraints:

• 1 ≤ students.length, sandwiches.length ≤ 100
• students.length == sandwiches.length
• sandwiches[i] is 0 or 1
• students[i] is 0 or 1

Solution (C++):

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        queue<int> studentQueue;
        int count[2] = {0, 0};
        // Count the number of students who prefer each type of sandwich
        for (int student : students) {
            studentQueue.push(student);
            count[student]++;
        }
        for (int i = 0; i < sandwiches.size(); i++) {
            // If there are no students left who want the current sandwich type, break the loop
            if (count[sandwiches[i]] == 0) {
                break;
            }
            // The student at the front of the queue wants the current sandwich
            while (studentQueue.front() != sandwiches[i]) {
                // Move the student to the back of the queue
                int student = studentQueue.front();
                studentQueue.pop();
                studentQueue.push(student);
            }
            // The student takes the sandwich and leaves
            studentQueue.pop();
            count[sandwiches[i]]--;
        }
        // The remaining students in the queue are those who are unable to eat
        return studentQueue.size();
    }
};
        

Explanation:

• Code Block:

The provided C++ solution is placed inside a <pre> tag, making it appear as preformatted code with the correct indentation and structure.

< and > are used for < and >, respectively, since this code is inside HTML.

• How to Use:

The C++ code can be copied into any C++ development environment (like Visual Studio, Code::Blocks, etc.).

You'll need to compile the code with g++ or any other C++ compiler.

The countStudents method can be used to solve the sandwich problem by passing two vectors (arrays) of integers as arguments:

        vector<int> students = {1, 1, 1, 0, 0, 1};
        vector<int> sandwiches = {1, 0, 0, 0, 1, 1};
        Solution sol;
        int result = sol.countStudents(students, sandwiches);
        cout << result;  // Outputs 3
        

• Whatsapp
• Tweet
• Share
• Share
• Share
• Share

Sign up here with your email