# Number of Students Unable to Eat Lunch
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-students-unable-to-eat-lunch)
Canonical: https://scaleengineer.com/dsa/problems/number-of-students-unable-to-eat-lunch
**Data structures:** Array, Stack, Queue
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers `0` and `1` respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a **stack**. At each step:

* 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 it** and go to the queue's end.

This continues until none of the queue students want to take the top sandwich and are thus unable to eat.

You are given two integer arrays `students` and `sandwiches` where `sandwiches[i]` is the type of the `i​​​​​​th` sandwich in the stack (`i = 0` is the top of the stack) and `students[j]` is the preference of the `j​​​​​​th` student in the initial queue (`j = 0` is the front of the queue). Return _the number of students that are unable to eat._

**Example 1:**

**Input:** students = [1,1,0,0], sandwiches = [0,1,0,1]
**Output:** 0 
**Explanation:**
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.

**Example 2:**

**Input:** students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
**Output:** 3

**Constraints:**

* `1 <= students.length, sandwiches.length <= 100`
* `students.length == sandwiches.length`
* `sandwiches[i]` is `0` or `1`.
* `students[i]` is `0` or `1`.

# Approaches
## Direct Simulation using a Queue
This approach directly simulates the process described in the problem statement. We use a queue to represent the line of students and an index to track the current sandwich on the top of the stack. The simulation proceeds step-by-step, with students either taking a sandwich or moving to the back of the line.
**Time:** O(N^2), where N is the number of students. In the worst-case scenario, for each of the N sandwiches served, we might have to cycle through all N students in the queue, leading to a quadratic runtime. · **Space:** O(N), where N is the number of students. This is required to store the student preferences in a queue.
**Pros:** It is highly intuitive as it directly follows the logic described in the problem.; The code is a straightforward translation of the problem's rules.
**Cons:** The time complexity of O(N^2) is inefficient for larger inputs.; Requires O(N) extra space to maintain the queue of students.
### Explanation
We begin by converting the `students` array into a `java.util.Queue`. We then loop, checking if the student at the front of the queue wants the current sandwich. If they do, they are removed from the queue, and we move to the next sandwich. If they don't, they are moved to the end of the queue. A crucial part of this simulation is detecting when the process gets stuck. This occurs when an entire rotation of the queue happens without any student taking a sandwich. We can track this by counting how many students in a row are sent to the back. If this count reaches the current number of students in the queue, it means no one can eat, and we stop the simulation. The number of students left in the queue is our answer.

```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        Queue<Integer> studentQueue = new LinkedList<>();
        for (int student : students) {
            studentQueue.add(student);
        }

        int sandwichIndex = 0;
        int unservedCount = 0;
        
        while (!studentQueue.isEmpty() && unservedCount < studentQueue.size()) {
            if (studentQueue.peek() == sandwiches[sandwichIndex]) {
                studentQueue.poll();
                sandwichIndex++;
                unservedCount = 0; // A student was served, reset the counter
            } else {
                // Student moves to the back of the queue
                studentQueue.add(studentQueue.poll());
                unservedCount++; // Increment the counter for unserved students
            }  
        }
        
        return studentQueue.size();
    }
}
```
### Algorithm
- Create a `Queue<Integer>` and add all elements from the `students` array to it.
- Initialize a sandwich pointer `sandwichIndex = 0`.
- Initialize a counter for consecutive unserved students, `unservedCount = 0`.
- Loop as long as the queue is not empty and `unservedCount` is less than the queue's current size.
  - If the student at the front of the queue (`studentQueue.peek()`) prefers the current sandwich (`sandwiches[sandwichIndex]`):
    - Remove the student from the queue (`studentQueue.poll()`).
    - Move to the next sandwich (`sandwichIndex++`).
    - Reset the unserved counter (`unservedCount = 0`) because a student was successfully served.
  - Else (the student does not want the sandwich):
    - Move the student to the back of the queue by dequeuing and then enqueuing them (`studentQueue.add(studentQueue.poll())`).
    - Increment the unserved counter (`unservedCount++`).
- The loop terminates when either the queue is empty or when `unservedCount` equals the queue size, indicating that no one in the queue wants the top sandwich.
- Return the final size of the queue.

## Counting Student Preferences
A more efficient approach recognizes that the specific order of students in the queue doesn't matter, only the total count of students for each preference. By pre-counting the student preferences, we can determine in linear time if a sandwich can be taken or if the process is stuck.
**Time:** O(N), where N is the number of students. We make one pass to count preferences and at most one pass through the sandwiches array. This results in a linear time complexity. · **Space:** O(1), as we only use a constant amount of extra space (an array of size 2) to store the counts of student preferences, regardless of the input size.
**Pros:** Extremely efficient with O(N) time complexity.; Optimal O(1) space complexity, as it only requires a fixed-size array for counts.; Simple implementation without complex data structures.
**Cons:** The logic is less direct than the simulation and requires an initial insight that the order of students with the same preference is irrelevant.
### Explanation
This method avoids the costly queue simulation. We start by making a single pass through the `students` array to get the total counts of students who prefer type 0 and type 1 sandwiches. Then, we iterate through the `sandwiches` array, which represents the stack. For each sandwich, we check our counts. If a student who prefers that sandwich type exists (i.e., the count for that type is greater than zero), we decrement the count, signifying that one student has eaten. If the count is zero, it means no student wants the current sandwich on top of the stack. At this point, the process halts, as no one will ever take this sandwich. The number of students unable to eat is simply the number of sandwiches that have not been distributed. If we successfully iterate through all sandwiches, it means everyone ate, and the answer is 0.

```java
class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] counts = new int[2]; // counts[0] for circular, counts[1] for square
        for (int student : students) {
            counts[student]++;
        }

        int n = sandwiches.length;
        for (int i = 0; i < n; i++) {
            int sandwich = sandwiches[i];
            if (counts[sandwich] > 0) {
                // A student with this preference exists and takes the sandwich
                counts[sandwich]--;
            } else {
                // No student wants this sandwich. All remaining students are unable to eat.
                // The number of remaining students is equal to the number of remaining sandwiches.
                return n - i;
            }
        }

        // All sandwiches were taken, so all students ate.
        return 0;
    }
}
```
### Algorithm
- First, count the number of students who prefer circular sandwiches (0) and square sandwiches (1). Store these in an array, say `counts`.
- Iterate through the `sandwiches` array from the top of the stack (index 0).
- For each `sandwich`:
  - Check if there is any student left who wants this type of sandwich (i.e., if `counts[sandwich] > 0`).
  - If yes, it means a student takes this sandwich. Decrement the corresponding count (`counts[sandwich]--`).
  - If no (`counts[sandwich] == 0`), it means no student wants the current sandwich. All remaining students want the other type, so they are stuck. The number of uneaten students is the number of remaining sandwiches. We can stop and return this count.
- If the loop completes, it means every student was served. Return 0.

# Solutions
### Java

```java
class Solution { public int countStudents ( int [] students , int [] sandwiches ) { int [] cnt = new int [ 2 ]; for ( int v : students ) { ++ cnt [ v ]; } for ( int v : sandwiches ) { if ( cnt [ v ]-- == 0 ) { return cnt [ v ^ 1 ]; } } return 0 ; } }
```

### CPP

```cpp
class Solution {
public:
  int countStudents(vector<int> &students, vector<int> &sandwiches) {
    int cnt[2] = {0};
    for (int &v : students)
      ++cnt[v];
    for (int &v : sandwiches) {
      if (cnt[v]-- == 0) {
        return cnt[v ^ 1];
      }
    }
    return 0;
  }
};

```

### Python

```python
class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int: cnt = Counter(students) for v in sandwiches: if cnt[v] == 0: return cnt[v ^ 1] cnt[v] -= 1 return 0

```