1116. Print Zero Even Odd - Leetcode Solution

Code Implementation

import threading

class ZeroEvenOdd:
    def __init__(self, n):
        self.n = n
        self.zero_sem = threading.Semaphore(1)
        self.even_sem = threading.Semaphore(0)
        self.odd_sem = threading.Semaphore(0)

    def zero(self, printNumber):
        for i in range(1, self.n + 1):
            self.zero_sem.acquire()
            printNumber(0)
            if i % 2 == 1:
                self.odd_sem.release()
            else:
                self.even_sem.release()

    def even(self, printNumber):
        for i in range(2, self.n + 1, 2):
            self.even_sem.acquire()
            printNumber(i)
            self.zero_sem.release()

    def odd(self, printNumber):
        for i in range(1, self.n + 1, 2):
            self.odd_sem.acquire()
            printNumber(i)
            self.zero_sem.release()

#include <functional>
#include <semaphore.h>
class ZeroEvenOdd {
private:
    int n;
    sem_t zero_sem, even_sem, odd_sem;
public:
    ZeroEvenOdd(int n) {
        this->n = n;
        sem_init(&zero_sem, 0, 1);
        sem_init(&even_sem, 0, 0);
        sem_init(&odd_sem, 0, 0);
    }

    void zero(function<void(int)> printNumber) {
        for (int i = 1; i <= n; ++i) {
            sem_wait(&zero_sem);
            printNumber(0);
            if (i % 2 == 1)
                sem_post(&odd_sem);
            else
                sem_post(&even_sem);
        }
    }

    void even(function<void(int)> printNumber) {
        for (int i = 2; i <= n; i += 2) {
            sem_wait(&even_sem);
            printNumber(i);
            sem_post(&zero_sem);
        }
    }

    void odd(function<void(int)> printNumber) {
        for (int i = 1; i <= n; i += 2) {
            sem_wait(&odd_sem);
            printNumber(i);
            sem_post(&zero_sem);
        }
    }
};

import java.util.concurrent.Semaphore;

class ZeroEvenOdd {
    private int n;
    private Semaphore zeroSem = new Semaphore(1);
    private Semaphore evenSem = new Semaphore(0);
    private Semaphore oddSem = new Semaphore(0);

    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    public void zero(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            zeroSem.acquire();
            printNumber.accept(0);
            if (i % 2 == 1) {
                oddSem.release();
            } else {
                evenSem.release();
            }
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        for (int i = 2; i <= n; i += 2) {
            evenSem.acquire();
            printNumber.accept(i);
            zeroSem.release();
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i += 2) {
            oddSem.acquire();
            printNumber.accept(i);
            zeroSem.release();
        }
    }
}

class Semaphore {
    constructor(count) {
        this.count = count;
        this.waiters = [];
    }
    async acquire() {
        if (this.count > 0) {
            this.count--;
            return;
        }
        await new Promise(resolve => this.waiters.push(resolve));
    }
    release() {
        if (this.waiters.length > 0) {
            this.waiters.shift()();
        } else {
            this.count++;
        }
    }
}

var ZeroEvenOdd = function(n) {
    this.n = n;
    this.zeroSem = new Semaphore(1);
    this.evenSem = new Semaphore(0);
    this.oddSem = new Semaphore(0);
};

ZeroEvenOdd.prototype.zero = async function(printNumber) {
    for (let i = 1; i <= this.n; i++) {
        await this.zeroSem.acquire();
        printNumber(0);
        if (i % 2 === 1) {
            this.oddSem.release();
        } else {
            this.evenSem.release();
        }
    }
};

ZeroEvenOdd.prototype.even = async function(printNumber) {
    for (let i = 2; i <= this.n; i += 2) {
        await this.evenSem.acquire();
        printNumber(i);
        this.zeroSem.release();
    }
};

ZeroEvenOdd.prototype.odd = async function(printNumber) {
    for (let i = 1; i <= this.n; i += 2) {
        await this.oddSem.acquire();
        printNumber(i);
        this.zeroSem.release();
    }
};

Problem Description

The "Print Zero Even Odd" problem asks you to implement a class that prints numbers in a specific order using three separate threads. Given a positive integer n, you must print numbers from 1 to n in the following sequence:
0 1 0 2 0 3 0 4 ...
That is, a zero is always printed before each number, and the numbers alternate between odd and even. Three different functions are provided, each to be run in its own thread:

zero(printNumber): prints zero n times.
even(printNumber): prints even numbers (2, 4, ..., n).
odd(printNumber): prints odd numbers (1, 3, ..., n).

The goal is to coordinate these threads so that the output matches the required pattern. Each number must be printed exactly once, and the zeros must alternate correctly with odd and even numbers.

Thought Process

At first glance, the problem seems to be about printing numbers in order, but the twist is that three different threads are responsible for printing different parts of the sequence. The challenge is to synchronize these threads so that:

Zero is always printed before each number.
Odd and even numbers are printed in the correct alternation.
No numbers or zeros are printed out of order or skipped.

A brute-force approach might try to use busy-waiting or shared variables to signal turns, but this is inefficient and can lead to race conditions. Instead, the problem is a classic example of thread synchronization, where we want threads to "take turns" in a specific sequence. Semaphores or other synchronization primitives can help us achieve this in a clean and efficient way.

Solution Approach

To solve this problem, we use semaphores (or similar synchronization mechanisms) to control which thread can print at any given time. Here is the step-by-step strategy:

Initialize Semaphores:
- One semaphore for the zero thread, initialized to 1 (so it starts first).
- One for the even thread, initialized to 0 (blocked at start).
- One for the odd thread, initialized to 0 (blocked at start).
Zero Thread Logic:
- For each number from 1 to n, acquire the zero semaphore (ensuring it's your turn).
- Print zero.
- If the next number is odd, release the odd semaphore; if even, release the even semaphore. This signals which thread should go next.
Odd/Even Thread Logic:
- Each waits for its respective semaphore to be released by the zero thread.
- When released, prints the next odd or even number.
- After printing, releases the zero semaphore so the zero thread can print the next zero.
Alternation:
- This cycle repeats, ensuring the output alternates as required: zero, number, zero, number, ...

Semaphores are used because they can block threads until they're allowed to proceed, making it easy to enforce the required sequence without busy-waiting or complex condition checks.

Example Walkthrough

Let's walk through the process with n = 3:
Initial state:

zero semaphore: 1
odd semaphore: 0
even semaphore: 0

Step-by-step:

Zero thread acquires its semaphore (count now 0), prints 0.
Since 1 is odd, releases odd semaphore (odd count now 1).
Odd thread acquires its semaphore, prints 1, releases zero semaphore (zero count now 1).
Zero thread acquires, prints 0.
Next number is even (2), so releases even semaphore.
Even thread acquires, prints 2, releases zero semaphore.
Zero thread acquires, prints 0.
Next number is odd (3), so releases odd semaphore.
Odd thread acquires, prints 3, releases zero semaphore.

Final Output: 0 1 0 2 0 3
Each thread waits for its turn, ensuring the sequence is correct.

Time and Space Complexity

Brute-force approach:
If you attempted to use busy-waiting or polling, the time complexity would be much higher and the program could waste CPU cycles, making it inefficient and potentially incorrect due to race conditions.

Optimized (Semaphore-based) approach:

Time Complexity: O(n) — Each print operation is done exactly once for each number from 1 to n, plus one zero before each number.
Space Complexity: O(1) — Only a constant number of semaphores and counters are used, regardless of input size.

The use of semaphores ensures that each thread is only active when it is supposed to print, with no wasted computation or memory.

Summary

The "Print Zero Even Odd" problem is a classic thread synchronization challenge. By using semaphores to control the order in which threads print their numbers, we achieve a clean and efficient solution. The key insight is to use synchronization primitives to enforce alternation, ensuring that the output sequence matches the required pattern. This approach avoids busy-waiting and race conditions, and demonstrates a fundamental concept in concurrent programming.

AlgoMap.io

Want Help Cracking FAANG?