Number of Students Unable to Eat Lunch

Easy
394.

Number of Students Unable to Eat Lunch

Number of Students Unable to Eat Lunch is an easy coding problem on arrays, simulation and stack, asked in Amazon and Adobe interviews.

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 <= 40
  • sandwiches.length == students.length
  • students[i] and sandwiches[i] are 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} students
 * @param {number[]} sandwiches
 * @return {number}
 */
var countStudents = function(students, sandwiches) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 40
  • sandwiches.length == students.length
  • students[i] and sandwiches[i] are 0 or 1.

Hints for Number of Students Unable to Eat Lunch

  1. Hint 1

    Rotating the queue never changes which preferences are still present, only their order.

  2. Hint 2

    So all that matters is how many students still want each kind.

  3. 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

  1. Count students wanting 0 and 1.
  2. Walk the sandwich stack: stop at the first kind nobody wants; otherwise serve and decrement.
  3. 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) - served

Java

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