Number of Students Unable to Eat Lunch — Problem & Solution
Number of Students Unable to Eat Lunch solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Number of Students Unable to Eat Lunch is an easy coding problem on arrays, simulation and stack, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Simulation, Stack, Queue
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Students queue for lunch. Sandwiches sit in a stack; sandwiches[0] is on top. Each sandwich is either round (0) or square (1), and each student prefers one kind.
The student at the front takes the top sandwich if it matches their preference, otherwise they go to the back of the queue. This repeats until nobody left in the queue wants the sandwich on top.
Return the number of students who never eat.
Example 1
Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0
Example 2
Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3
Example 3
Input: students = [0], sandwiches = [1]
Output: 1
Constraints
1 <= students.length <= 40sandwiches.length == students.lengthstudents[i] and sandwiches[i] are 0 or 1.
Hints for Number of Students Unable to Eat Lunch
Hint 1
Rotating the queue never changes which preferences are still present, only their order.
Hint 2
So all that matters is how many students still want each kind.
Hint 3
Walk the sandwich stack, serving while someone still wants the top one; stop at the first sandwich nobody wants.
How to solve Number of Students Unable to Eat Lunch
Rotating the queue never changes which preferences remain, so count how many students want each kind and serve sandwiches from the top while someone wants it.
Approach
- Count students wanting 0 and 1.
- Walk the sandwich stack: stop at the first kind nobody wants; otherwise serve and decrement.
- Return
n - served.
Why it works
If any student wants the top sandwich, the queue will eventually rotate that student to the front; if none does, the process stalls forever.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The queue's order is irrelevant — only the counts matter.
Reference solution
Python
def countStudents(students, sandwiches) -> int:
want = [0, 0]
for s in students:
want[s] += 1
served = 0
for kind in sandwiches:
if want[kind] == 0:
break
want[kind] -= 1
served += 1
return len(students) - servedJava
public static int countStudents(int[] students, int[] sandwiches) {
int[] want = new int[2];
for (int s : students) want[s]++;
int served = 0;
for (int kind : sandwiches) {
if (want[kind] == 0) break;
want[kind]--;
served++;
}
return students.length - served;
}C++
int countStudents(vector<int>& students, vector<int>& sandwiches) {
int want[2] = {0, 0};
for (int s : students) want[s]++;
int served = 0;
for (int kind : sandwiches) {
if (want[kind] == 0) break;
want[kind]--;
served++;
}
return (int) students.size() - served;
}JavaScript
var countStudents = function(students, sandwiches) {
const want = [0, 0];
for (let i = 0; i < students.length; i++) want[students[i]]++;
let served = 0;
for (let i = 0; i < sandwiches.length; i++) {
if (want[sandwiches[i]] === 0) break;
want[sandwiches[i]]--;
served++;
}
return students.length - served;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure