Talentd
FleetCode
Make and follow sheets.Sign in

Print Zero Even Odd solution and explanation

MediumConcurrency7 min read62.0% acceptanceUpdated 9 Apr 2026
Leetcode 1116 Print Zero Even Odd (Java Concurrency)TheAnalyticGuy · 14:57 · 2K viewsWatch on YouTube
7 more videos on this problem
  1. Leetcode 1116 Print Zero Even Odd (Java Concurrency)TheAnalyticGuy · 14:57 · 2K views
  2. 1116. Print Zero Even Odd - Daily Leetcode (Day 31)yeetcode · 31:25 · 240 views
  3. No Sound Leetcode 1116: Print Zero Even OddExtremeProgrammer · 3:44 · 149 views
  4. Leetcode 1116 Print Zero Even Odd - Java Multithreading QuestionAlgorithmicIQ · 14:26 · 147 views
  5. Print Zero Even Odd, Medium, LeetCode 1116H William Polenz · 17:37 · 138 views
  6. Print Zero Even Odd | LeetCode 1116 | Java & Go Concurrency SolutionCoding Thor · 9:46 · 133 views
  7. Java Multithreading Interview Questions | Part 3 | Semaphore Explained with LeetCode 1116Engineer To Engineer · 6:49 · 15 views
  8. 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) 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.

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.

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.

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.

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).

#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);
        }
    }
};
Try this approach in the editor

Complexity comparison

ApproachComplexity
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–

Complexity analysis

ApproachTimeSpaceWhen to Use
Mutex and Condition VariablesO(n)O(1)When demonstrating low-level thread coordination and lock-based synchronization
SemaphoresO(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.

Comments

Now write it yourselfClose this page and solve Print Zero Even Odd in the editor, without looking.
Practise Print Zero Even Odd