Print Zero Even Odd - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

MediumConcurrency12 min readAsked at: Goldman Sachs, Google

Practice this problem

Problem Statement

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

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.

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.

Code

Python C

Python

Complexity

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.

Try this approach in the editor →

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.

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.

Code

Java JavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

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 z controls the execution of the zero function. When the value of semaphore z is 1, the zero function can be executed. After execution, the value of semaphore z is set to 0, and the value of semaphore e or o is set to 1, depending on whether the even function or the odd function needs to be executed next.
Semaphore e controls the execution of the even function. When the value of semaphore e is 1, the even function can be executed. After execution, the value of semaphore z is set to 1, and the value of semaphore e is set to 0.
Semaphore o controls the execution of the odd function. When the value of semaphore o is 1, the odd function can be executed. After execution, the value of semaphore z is set to 1, and the value of semaphore o is set to 0.

The time complexity is O(n), and the space complexity is O(1).

Code

Python Java C++

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Approach 1: Using Mutex and Condition Variables	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: Using Semaphores	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.
Multithreading + Semaphore	—

Detailed 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

Video Solution

LeetCode Concurrency Print Zero Odd Even • CppNuts • 2,544 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Print Zero Even Odd with our built-in code editor and test cases.

Practice on FleetCode

Fizz Buzz Multithreaded

Print FooBar Alternately

Problem Info

DifficultyMedium

Acceptance62.0%

Approaches3

Reading time12 min

Asked at

Goldman Sachs Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Using Mutex and Condition Variables

Code

Complexity

Approach 2: Approach 2: Using Semaphores

Code

Complexity

Approach 3: Multithreading + Semaphore

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents