Print Zero Even Odd solution and explanation
7 more videos on this problem
Leetcode 1116 Print Zero Even Odd (Java Concurrency)TheAnalyticGuy · 14:57 · 2K views
1116. Print Zero Even Odd - Daily Leetcode (Day 31)yeetcode · 31:25 · 240 views
No Sound Leetcode 1116: Print Zero Even OddExtremeProgrammer · 3:44 · 149 views
Leetcode 1116 Print Zero Even Odd - Java Multithreading QuestionAlgorithmicIQ · 14:26 · 147 views
Print Zero Even Odd, Medium, LeetCode 1116H William Polenz · 17:37 · 138 views
Print Zero Even Odd | LeetCode 1116 | Java & Go Concurrency SolutionCoding Thor · 9:46 · 133 views
Java Multithreading Interview Questions | Part 3 | Semaphore Explained with LeetCode 1116Engineer To Engineer · 6:49 · 15 views
LeetCode Concurrency Print Zero Odd EvenCppNuts · 10:09 · 2K views
The 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)prints7to 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 output0'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 numbernthat represents the numbers that should be printed.void zero(printNumber)CallsprintNumberto output one zero.void even(printNumber)CallsprintNumberto output one even number.void odd(printNumber)CallsprintNumberto 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
Approach overview
Problem Overview: You control three threads: one prints 0, one prints even numbers, and one prints odd numbers. The output must follow the pattern 0 1 0 2 0 3 ... 0 n. The challenge is coordinating thread execution so the correct thread prints at the correct time without race conditions.
Approach 1: Using Mutex and Condition Variables (O(n) time, O(1) space)
This approach coordinates threads using a shared mutex and condition variables. A shared state variable determines which thread should run next: zero, odd, or even. Each thread acquires the mutex, checks the state, and waits on a condition variable if it is not its turn. When the correct thread prints its value, it updates the state and signals the next waiting thread using notify or signal. The zero thread runs before every number, alternating between odd and even threads depending on the current value. The complexity is O(n) because each number is printed once, and the synchronization overhead is constant. Space complexity is O(1) since only a few shared variables are maintained.
This technique relies on primitives from concurrency such as mutex locks and condition variables. It provides fine-grained control and avoids busy waiting. Systems programming interviews sometimes prefer this method because it demonstrates understanding of thread coordination and lock-based synchronization.
Approach 2: Using Semaphores (O(n) time, O(1) space)
Semaphores simplify the coordination logic by directly controlling which thread is allowed to proceed. Three semaphores are used: one for the zero thread, one for odd numbers, and one for even numbers. The zero semaphore starts with value 1 so the zero thread prints first. After printing 0, the zero thread releases either the odd or even semaphore depending on the next number. The corresponding thread prints its value and then releases the zero semaphore to continue the sequence.
This pattern ensures only one thread runs at a time while preserving the required order. Every print operation corresponds to one semaphore acquire and release, giving O(n) total operations. Space usage remains O(1). Semaphores are a classic tool in concurrency control and often appear in interview problems involving ordered thread execution. If you are comfortable with semaphores, this implementation is typically shorter and easier to reason about than condition variables.
Recommended for interviews: The semaphore solution is usually the cleanest and easiest to explain under time pressure. It clearly expresses which thread runs next using semaphore permits. The mutex + condition variable approach is also valid and demonstrates deeper knowledge of synchronization primitives. Showing the ability to model thread states and prevent race conditions is what interviewers typically look for in concurrency problems.
Approach 1: Approach 1: Using Mutex and Condition Variables
This approach uses mutexes and condition variables to synchronize the threads. The zero function signals either the odd or even function after printing a zero. The even and odd functions wait for their respective conditions to be signaled to proceed. This ensures that the numbers are printed in the correct order.
from threading import Lock, Condition
class ZeroEvenOdd:
def __init__(self, n):
self.n = n
self.zero_lock = Lock()
self.even_lock = Lock()
self.odd_lock = Lock()
self.zero_lock.acquire()
self.even_lock.acquire()
def zero(self, printNumber):
for i in range(1, self.n + 1):
self.zero_lock.acquire()
printNumber(0)
if i % 2 == 0:
self.even_lock.release()
else:
self.odd_lock.release()
def even(self, printNumber):
for i in range(2, self.n + 1, 2):
self.even_lock.acquire()
printNumber(i)
self.zero_lock.release()
def odd(self, printNumber):
for i in range(1, self.n + 1, 2):
self.odd_lock.acquire()
printNumber(i)
self.zero_lock.release()#include <stdio.h>
#include <pthread.h>
struct ZeroEvenOdd {
int n;
int current;
pthread_mutex_t lock;
pthread_cond_t zero_cond, odd_cond, even_cond;
};
void zero(struct ZeroEvenOdd *z, void (*printNumber)(int)) {
for (int i = 1; i <= z->n; ++i) {
pthread_mutex_lock(&z->lock);
while (z->current != 0) {
pthread_cond_wait(&z->zero_cond, &z->lock);
}
printNumber(0);
z->current = (i % 2 == 0) ? 2 : 1;
if (z->current == 1) {
pthread_cond_signal(&z->odd_cond);
} else {
pthread_cond_signal(&z->even_cond);
}
pthread_mutex_unlock(&z->lock);
}
}
void even(struct ZeroEvenOdd *z, void (*printNumber)(int)) {
for (int i = 2; i <= z->n; i += 2) {
pthread_mutex_lock(&z->lock);
while (z->current != 2) {
pthread_cond_wait(&z->even_cond, &z->lock);
}
printNumber(i);
z->current = 0;
pthread_cond_signal(&z->zero_cond);
pthread_mutex_unlock(&z->lock);
}
}
void odd(struct ZeroEvenOdd *z, void (*printNumber)(int)) {
for (int i = 1; i <= z->n; i += 2) {
pthread_mutex_lock(&z->lock);
while (z->current != 1) {
pthread_cond_wait(&z->odd_cond, &z->lock);
}
printNumber(i);
z->current = 0;
pthread_cond_signal(&z->zero_cond);
pthread_mutex_unlock(&z->lock);
}
}Here, we initialize three Lock objects: zero_lock, even_lock, and odd_lock. At the start, we acquire zero_lock to ensure Thread A (zero) is the one beginning the sequence. The even_lock and odd_lock are also acquired initially, meaning the even and odd threads will be waiting. The zero method prints 0 and releases the lock for either odd or even methods based on the sequence. This ensures the correct sequence is maintained.
Time Complexity: O(n), since we loop through n iterations for each function.
Space Complexity: O(1), as we use a fixed amount of additional memory for lock objects.
Approach 2: Approach 2: Using Semaphores
Semaphores are used to manage access to shared resources by multiple threads in a concurrent system. In this solution, semaphores manage the permit distribution so that no two threads execute their print function simultaneously. This controls the order of function executions.
import java.util.concurrent.Semaphore;
class ZeroEvenOdd {
private int n;
private Semaphore zeroSemaphore = new Semaphore(1);
private Semaphore oddSemaphore = new Semaphore(0);
private Semaphore evenSemaphore = new Semaphore(0);
public ZeroEvenOdd(int n) {
this.n = n;
}
public void zero(IntConsumer printNumber) throws InterruptedException {
for (int i = 1; i <= n; i++) {
zeroSemaphore.acquire();
printNumber.accept(0);
if (i % 2 == 1) {
oddSemaphore.release();
} else {
evenSemaphore.release();
}
}
}
public void odd(IntConsumer printNumber) throws InterruptedException {
for (int i = 1; i <= n; i += 2) {
oddSemaphore.acquire();
printNumber.accept(i);
zeroSemaphore.release();
}
}
public void even(IntConsumer printNumber) throws InterruptedException {
for (int i = 2; i <= n; i += 2) {
evenSemaphore.acquire();
printNumber.accept(i);
zeroSemaphore.release();
}
}
}const { Semaphore } = require('async-mutex');
class ZeroEvenOdd {
constructor(n) {
this.n = n;
this.zeroSemaphore = new Semaphore(1);
this.oddSemaphore = new Semaphore(0);
this.evenSemaphore = new Semaphore(0);
}
async zero(printNumber) {
for (let i = 1; i <= this.n; i++) {
await this.zeroSemaphore.acquire();
printNumber(0);
if (i % 2 === 1) {
this.oddSemaphore.release();
} else {
this.evenSemaphore.release();
}
}
}
async odd(printNumber) {
for (let i = 1; i <= this.n; i += 2) {
await this.oddSemaphore.acquire();
printNumber(i);
this.zeroSemaphore.release();
}
}
async even(printNumber) {
for (let i = 2; i <= this.n; i += 2) {
await this.evenSemaphore.acquire();
printNumber(i);
this.zeroSemaphore.release();
}
}
}This Java solution utilizes the Semaphore class for synchronization. Initially, the zeroSemaphore permits one thread to print '0'. Subsequent odd or even semaphore releases permit specific threads to print their respective numbers. By carefully releasing and acquiring these semaphores, the correct order is maintained.
Time Complexity: O(n), each thread iterates through a portion of n values.
Space Complexity: O(1), as semaphore footprint is constant regardless of n.
Approach 3: Multithreading + Semaphore
We use three semaphores z, e, and o to control the execution order of the three threads, where z is initially set to 1, and e and o are set to 0.
- Semaphore
zcontrols the execution of thezerofunction. When the value of semaphorezis1, thezerofunction can be executed. After execution, the value of semaphorezis set to0, and the value of semaphoreeorois set to1, depending on whether theevenfunction or theoddfunction needs to be executed next. - Semaphore
econtrols the execution of theevenfunction. When the value of semaphoreeis1, theevenfunction can be executed. After execution, the value of semaphorezis set to1, and the value of semaphoreeis set to0. - Semaphore
ocontrols the execution of theoddfunction. When the value of semaphoreois1, theoddfunction can be executed. After execution, the value of semaphorezis set to1, and the value of semaphoreois set to0.
The time complexity is O(n), and the space complexity is O(1).
#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);
}
}
};Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Mutex and Condition Variables | Time Complexity: O(n), since we loop through n iterations for each function. |
| Approach 2: Using Semaphores | Time Complexity: O(n), each thread iterates through a portion of n values. |
| Multithreading + Semaphore | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Mutex and Condition Variables | O(n) | O(1) | When demonstrating low-level thread coordination and lock-based synchronization |
| Semaphores | O(n) | O(1) | Preferred for clarity and simpler ordered thread execution logic |
Frequently asked questions
Is Print Zero Even Odd easy or hard?
Print Zero Even Odd is typically rated Medium because the logic itself is simple but implementing correct thread synchronization can be tricky. Developers must prevent race conditions and ensure threads execute in the exact required order.
How to solve Print Zero Even Odd in O(n)?
Use synchronization primitives to enforce execution order between threads. With semaphores, the zero thread prints 0 and releases either the odd or even semaphore. The corresponding thread prints its number and signals the zero thread again. Each step happens once per number, resulting in O(n) time.
Print Zero Even Odd Python or Java solution
Python implementations often use a mutex with condition variables from the threading module. Java solutions commonly use Semaphore from java.util.concurrent. Both approaches maintain O(n) time complexity while ensuring threads print in the correct sequence.
What is the best approach for Print Zero Even Odd?
The semaphore-based approach is generally the cleanest solution. It uses three semaphores to control which thread prints next, ensuring the sequence 0, number, 0, number continues correctly. This approach runs in O(n) time with O(1) extra space and avoids complex condition checks.
What data structure is used in Print Zero Even Odd?
The problem does not rely on traditional data structures like arrays or hash maps. Instead, it uses concurrency primitives such as mutex locks, condition variables, or semaphores to coordinate thread execution and maintain the correct printing order.
What is the time complexity of Print Zero Even Odd?
The time complexity is O(n) because each number from 1 to n is printed once and each print involves a constant number of synchronization operations. Space complexity is O(1) since only a few shared variables or semaphores are used.
Is Print Zero Even Odd asked at Google, Amazon, or Meta?
Concurrency coordination problems like Print Zero Even Odd appear in interviews at companies that test multithreading knowledge, including Google, Amazon, and Meta. Interviewers use them to evaluate understanding of synchronization primitives such as mutexes, condition variables, and semaphores.
