1116.Print_Zero_Even_Odd(Medium).md

1116. Print Zero Even Odd (Medium)

Date and Time: Feb 19, 2025, 00:15 (EST)

Link: https://leetcode.com/problems/print-zero-even-odd

Question:

You have a function printNumber that can be called with an integer parameter and prints it to the console.

• For example, calling printNumber(7) prints 7 to the console.

You are given an instance of the class ZeroEvenOdd that has three functions: zero, even, and odd. The same instance of ZeroEvenOdd will be passed to three different threads:

• Thread A: calls zero() that should only output 0's.
• Thread B: calls even() that should only output even numbers.
• Thread C: calls odd() that should only output odd numbers.

Modify the given class to output the series "010203040506..." where the length of the series must be 2n.

Implement the ZeroEvenOdd class:

• ZeroEvenOdd(int n): Initializes the object with the number n that represents the numbers that should be printed.
• void zero(printNumber): Calls printNumber to output one zero.
• void even(printNumber): Calls printNumber to output one even number.
• void odd(printNumber): Calls printNumber to output one odd number.

Example 1:

Input: n = 2
Output: "0102"

Explanation: There are three threads being fired asynchronously. One of them calls zero(), the other calls even(), and the last one calls odd().
"0102" is the correct output.

Example 2:

Input: n = 5
Output: "0102030405"

Constraints:

• 1 <= n <= 1000

Walk-through:

1. Define three semophores for zero(), even(), odd(). We initialize the semophore of zero() with priority 1 (sem_init(&sem_zero, 0, 1);), so we can always run sem_zero with higher priority.

2. We start at i = 1, and each time it only increments by 1 in zero(). We identify if we should call odd() next or even() next by i, if i is odd, we unlock sem_odd to execute odd(), otherwise, we unlock sem_even for even().

3. odd() starts with i = 1, self-increment by 2 each time. So we can always printNumber() the odd number. After we print, we unlock sem_zero again to back to zero(). Same logic applies to even().

C++:

class ZeroEvenOdd {

private:
    int n;
    sem_t sem_zero;
    sem_t sem_even;
    sem_t sem_odd;

public:
    ZeroEvenOdd(int n) {
        this->n = n;
        sem_init(&sem_zero, 0, 1);   // Give priority to semophore_zero to start first
        sem_init(&sem_even, 0, 0);
        sem_init(&sem_odd, 0, 0);
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        for (int i = 1; i < n+1; i++) {
            // Wait to be unlocked
            sem_wait(&sem_zero);
            printNumber(0);
            // Identify to unlock odd or even base on i
            if (i % 2 == 1) {
                sem_post(&sem_odd);
            } else {
                sem_post(&sem_even);
            }
        }
    }

    void even(function<void(int)> printNumber) {
        for (int i = 2; i < n+1; i+=2) {
            sem_wait(&sem_even);    // Wait to be unlocked
            printNumber(i);
            sem_post(&sem_zero);    // Get back to zero()
        }
    }

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