# 08.04.2024 [1700. Number of Students Unable to Eat Lunch]
First sandwitch not eaten by any while popped from a queue #easy
08.04.2024
1700. Number of Students Unable to Eat Lunch easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/564
Problem TLDR
First sandwitch not eaten by any while popped from a queue #easy
Intuition
First, understant the problem: we searching the first sandwitch
which none of the students are able to eat.
The simulation code is straighforward and takes O(n^2) time which is accepted.
However, we can count how many students are 0
-eaters and how many 1
-eaters, then stop when none are able to eat current sandwitch.
Approach
We can use two counters or one array. How many lines of code can you save?
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun countStudents(students: IntArray, sandwiches: IntArray): Int {
val count = IntArray(2)
for (s in students) count[s]++
for ((i, s) in sandwiches.withIndex())
if (--count[s] < 0) return students.size - i
return 0
}
pub fn count_students(students: Vec<i32>, sandwiches: Vec<i32>) -> i32 {
let (mut count, n) = (vec![0; 2], students.len());
for s in students { count[s as usize] += 1 }
for (i, &s) in sandwiches.iter().enumerate() {
count[s as usize] -= 1;
if count[s as usize] < 0 { return (n - i) as i32 }
}; 0
}