# Print Zero Even Odd
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/print-zero-even-odd)
Canonical: https://scaleengineer.com/dsa/problems/print-zero-even-odd
---
## Problem
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`

# Approaches
## Using `synchronized`, `wait()`, and `notifyAll()`
This approach uses Java's fundamental concurrency primitives: `synchronized` blocks and the `wait()`/`notifyAll()` methods. A shared state variable is used to coordinate the three threads, ensuring they print in the correct `0, 1, 0, 2, 0, 3, ...` sequence.
**Time:** O(n) - Each number in the sequence is printed once. The total time is proportional to `n`, though with some overhead from thread context switching. · **Space:** O(1) - Constant extra space is used for the state variable.
**Pros:** Uses basic, built-in Java synchronization, making it a fundamental concept to understand.; The logic is contained within the methods without needing external lock objects.
**Cons:** The use of `notifyAll()` is inefficient. It wakes up all waiting threads, even those that cannot proceed. This leads to unnecessary context switches and lock contention, a phenomenon known as the 'thundering herd' problem.
### Explanation
In this method, we rely on the object's monitor lock. A state variable, `turn`, dictates which thread is allowed to execute. The `zero` thread starts first as `turn` is initialized to 0. It prints a zero, then decides whether the `odd` or `even` thread should run next based on the current iteration number, updates `turn` accordingly, and calls `notifyAll()`. The `odd` and `even` threads wait for their respective `turn` value. Once awakened and their condition is met, they print their number, set `turn` back to 0 for the `zero` thread, and also call `notifyAll()`. Using `synchronized` on the methods ensures that only one thread can modify the shared state at a time.
### Algorithm
- A shared integer variable, `turn`, is used to track the current state (0 for `zero`, 1 for `odd`, 2 for `even`).
- All three methods (`zero`, `even`, `odd`) are declared `synchronized`, using the object's intrinsic lock for mutual exclusion.
- Inside each method, a thread waits in a `while` loop, calling `wait()` until the `turn` variable matches its required state. The loop is necessary to guard against spurious wakeups.
- After printing its number, a thread updates the `turn` variable to signal which thread should run next.
- It then calls `notifyAll()` to wake up all other waiting threads. The awakened threads re-check the `turn` variable, and the correct one proceeds.

## Using `ReentrantLock` and `Condition`
This approach enhances synchronization by using `ReentrantLock` and `Condition` objects from the `java.util.concurrent.locks` package. It provides more fine-grained control over thread signaling, which is more efficient than the `notifyAll()`-based method.
**Time:** O(n) - The overall complexity is linear, but it's generally faster than the `notifyAll()` approach due to more efficient thread management. · **Space:** O(1) - Constant extra space is used for the lock, condition objects, and state variable.
**Pros:** More efficient than `notifyAll()` because `signal()` wakes up only one specific thread, preventing the 'thundering herd' problem.; `ReentrantLock` offers more features than intrinsic locks, such as timed waits and interruptible lock acquisition.
**Cons:** The code is more verbose than the `synchronized` version due to the need for explicit `lock()` and `unlock()` calls, typically within a `try...finally` block.
### Explanation
By using separate `Condition` objects, we can create distinct waiting queues for each thread. When the `zero` thread finishes, it doesn't just wake up a random thread; it specifically signals the condition for the next thread in the sequence (`oddTurn` or `evenTurn`). This targeted signaling (`signal()`) is a major improvement over `notifyAll()`, as it wakes up only one relevant thread, avoiding the thundering herd problem. This reduces unnecessary wake-ups, context switches, and lock contention, leading to better performance.
### Algorithm
- An explicit `ReentrantLock` is used for mutual exclusion instead of an intrinsic lock.
- Three `Condition` objects (`zeroTurn`, `evenTurn`, `oddTurn`) are created from the lock, one for each thread's waiting condition.
- A shared `turn` variable (0, 1, or 2) still tracks the state.
- Each thread acquires the `lock`, then waits on its specific `Condition` object (e.g., `even` thread calls `evenTurn.await()`) until its turn arrives.
- After printing, a thread updates the `turn` state and calls `signal()` on the `Condition` object of the *next* thread in the sequence.
- The lock is released in a `finally` block to ensure it's always unlocked.

## Using Semaphores
This is a highly elegant and efficient solution that uses semaphores to manage the execution order. Semaphores act as permits that threads must acquire to proceed, providing a clean and direct way to control the sequence of operations.
**Time:** O(n) - A very performant linear time solution due to the efficiency of semaphores. · **Space:** O(1) - Constant extra space is used for the three semaphore objects.
**Pros:** The code is very concise and directly reflects the turn-based nature of the problem.; Highly efficient, as semaphore operations are typically implemented with low-level, optimized system calls.; Avoids explicit state variables and locking, which can reduce code complexity and potential for errors.
**Cons:** The concept of semaphores might be less familiar to some developers compared to intrinsic locks.
### Explanation
This approach models the problem as a hand-off of a single execution permit. The `semZero` starts with the permit. The `zero` thread acquires it, does its work, and then releases a permit to the appropriate next semaphore (`semOdd` or `semEven`). The corresponding thread then acquires that permit, does its work, and releases a permit back to `semZero`. This cycle continues until all numbers are printed. This method is very clean because it doesn't require an explicit shared state variable like `turn` or explicit locking. The state is implicitly managed by which semaphore currently holds a permit.
### Algorithm
- Three `Semaphore` objects are used: `semZero`, `semEven`, and `semOdd`.
- `semZero` is initialized with 1 permit, allowing the `zero` thread to run first. `semEven` and `semOdd` are initialized with 0 permits, forcing them to block initially.
- Each thread's main loop starts by calling `acquire()` on its corresponding semaphore. This blocks the thread until a permit is available.
- The `zero` thread, after printing 0, calls `release()` on either `semOdd` or `semEven` to grant a permit to the next thread.
- The `odd` and `even` threads, after printing their numbers, call `release()` on `semZero` to pass control back to the `zero` thread.

# Solutions
### Java

```java
class ZeroEvenOdd { private int n ; private Semaphore z = new Semaphore ( 1 ); private Semaphore e = new Semaphore ( 0 ); private Semaphore o = new Semaphore ( 0 ); public ZeroEvenOdd ( int n ) { this . n = n ; } // printNumber.accept(x) outputs "x", where x is an integer. public void zero ( IntConsumer printNumber ) throws InterruptedException { for ( int i = 0 ; i < n ; ++ i ) { z . acquire ( 1 ); printNumber . accept ( 0 ); if ( i % 2 == 0 ) { o . release ( 1 ); } else { e . release ( 1 ); } } } public void even ( IntConsumer printNumber ) throws InterruptedException { for ( int i = 2 ; i <= n ; i += 2 ) { e . acquire ( 1 ); printNumber . accept ( i ); z . release ( 1 ); } } public void odd ( IntConsumer printNumber ) throws InterruptedException { for ( int i = 1 ; i <= n ; i += 2 ) { o . acquire ( 1 ); printNumber . accept ( i ); z . release ( 1 ); } } }
```

### CPP

```cpp
#include <semaphore.h> class ZeroEvenOdd { private: int n ; sem_t z , e , o ; public: ZeroEvenOdd ( int n ) { this -> n = n ; sem_init ( & z , 0 , 1 ); sem_init ( & e , 0 , 0 ); sem_init ( & o , 0 , 0 ); } // printNumber(x) outputs "x", where x is an integer. void zero ( function < void ( int ) > printNumber ) { for ( int i = 0 ; i < n ; ++ i ) { sem_wait ( & z ); printNumber ( 0 ); if ( i % 2 == 0 ) { sem_post ( & o ); } else { sem_post ( & e ); } } } void even ( function < void ( int ) > printNumber ) { for ( int i = 2 ; i <= n ; i += 2 ) { sem_wait ( & e ); printNumber ( i ); sem_post ( & z ); } } void odd ( function < void ( int ) > printNumber ) { for ( int i = 1 ; i <= n ; i += 2 ) { sem_wait ( & o ); printNumber ( i ); sem_post ( & z ); } } };
```

### Python

```python
from threading import Semaphore class ZeroEvenOdd : def __init__ ( self , n ): self . n = n self . z = Semaphore ( 1 ) self . e = Semaphore ( 0 ) self . o = Semaphore ( 0 ) # printNumber(x) outputs "x", where x is an integer. def zero ( self , printNumber : 'Callable[[int], None]' ) -> None : for i in range ( self . n ): self . z . acquire () printNumber ( 0 ) if i % 2 == 0 : # 'i%2==1' will have wrong answer "0201" self . o . release () else : self . e . release () def even ( self , printNumber : 'Callable[[int], None]' ) -> None : for i in range ( 2 , self . n + 1 , 2 ): self . e . acquire () printNumber ( i ) self . z . release () def odd ( self , printNumber : 'Callable[[int], None]' ) -> None : for i in range ( 1 , self . n + 1 , 2 ): self . o . acquire () printNumber ( i ) self . z . release ()
```