Problem Description

This is a multithreading synchronization problem where you need to coordinate three threads to print a specific sequence of numbers.

You're given a class ZeroEvenOdd that will be shared among three threads:

• Thread A repeatedly calls zero() to print 0
• Thread B repeatedly calls even() to print even numbers (2, 4, 6, ...)
• Thread C repeatedly calls odd() to print odd numbers (1, 3, 5, ...)

The goal is to synchronize these threads so they produce the output pattern: "010203040506..." up to number n.

The pattern follows this rule:

• Before each positive number (1, 2, 3, ..., n), a 0 must be printed
• The positive numbers alternate between odd and even in ascending order
• The total length of the output sequence is 2n (n zeros and n positive numbers)

For example, if n = 5, the output should be: "0102030405"

The class provides these methods:

• ZeroEvenOdd(int n): Constructor that initializes with the maximum number n
• zero(printNumber): Should print 0 using the provided printNumber function
• even(printNumber): Should print the next even number using printNumber
• odd(printNumber): Should print the next odd number using printNumber

The challenge is to implement proper synchronization using semaphores so that:

1. Zero is always printed before each positive number
2. Odd and even numbers alternate correctly in sequence
3. No race conditions or deadlocks occur

The solution uses three semaphores to control the execution order:

• Semaphore z (initially 1): Controls when zero() can execute
• Semaphore e (initially 0): Controls when even() can execute
• Semaphore o (initially 0): Controls when odd() can execute

The zero() method determines whether to release the odd or even semaphore based on which positive number comes next in the sequence.

Intuition

The key insight is recognizing that this is a producer-consumer pattern with a specific ordering requirement. We need to enforce a strict sequence: 0 → odd → 0 → even → 0 → odd → ...

Let's think about the execution flow:

1. A zero must always come first
2. After each zero, we need either an odd or even number
3. After each positive number, we need another zero

This creates a cyclic dependency where each thread must wait for specific other threads to complete before proceeding.

The natural approach is to use semaphores as "permission tokens" that threads pass to each other. Think of it like a relay race where only the runner with the baton can run:

• Initially, only the zero() thread has permission to run (baton)
• After zero() prints, it needs to decide who gets the baton next
• The pattern shows odd numbers come at positions 1, 3, 5... and even numbers at positions 2, 4, 6...
• So zero() can track which iteration it's on: if i % 2 == 0, pass the baton to odd(), otherwise to even()

Why three semaphores? Each thread needs its own "wait signal":

• z semaphore: Controls when zero() can run (starts with 1 since zero goes first)
• o semaphore: Controls when odd() can run (starts with 0, must wait)
• e semaphore: Controls when even() can run (starts with 0, must wait)

The beauty of this solution is that each thread, after completing its work, "wakes up" the next thread in the sequence by releasing the appropriate semaphore. The even() and odd() threads always give control back to zero(), while zero() alternates between giving control to odd() and even().

This creates a perfect choreography where threads take turns in the exact order needed to produce the desired output pattern.

Solution Approach

The implementation uses three semaphores to orchestrate the thread execution order. Let's walk through how each component works:

Initialization:

self.z = Semaphore(1)  # Zero thread can start immediately
self.e = Semaphore(0)  # Even thread must wait
self.o = Semaphore(0)  # Odd thread must wait

The semaphore values represent how many times a thread can proceed without blocking. Setting z to 1 allows the zero() thread to run first, while e and o at 0 means those threads will block until signaled.

Zero Thread Logic:

def zero(self, printNumber):
    for i in range(self.n):
        self.z.acquire()    # Wait for permission to print zero
        printNumber(0)      # Print 0
        if i % 2 == 0:
            self.o.release()  # Allow odd thread to run
        else:
            self.e.release()  # Allow even thread to run

The zero() function runs n times (once before each positive number). After printing 0, it determines which thread should run next:

• On iterations 0, 2, 4... (even indices), it releases the odd semaphore for numbers 1, 3, 5...
• On iterations 1, 3, 5... (odd indices), it releases the even semaphore for numbers 2, 4, 6...

Odd Thread Logic:

def odd(self, printNumber):
    for i in range(1, self.n + 1, 2):  # Generate 1, 3, 5, ...
        self.o.acquire()    # Wait for permission from zero thread
        printNumber(i)      # Print the odd number
        self.z.release()    # Give control back to zero thread

The odd thread iterates through odd numbers from 1 to n. Each iteration:

1. Waits for the o semaphore to be released by zero()
2. Prints the current odd number
3. Releases the z semaphore to allow zero() to continue

Even Thread Logic:

def even(self, printNumber):
    for i in range(2, self.n + 1, 2):  # Generate 2, 4, 6, ...
        self.e.acquire()    # Wait for permission from zero thread
        printNumber(i)      # Print the even number
        self.z.release()    # Give control back to zero thread

Similar to the odd thread, but iterates through even numbers starting from 2.

Execution Flow Example (n=3):

1. zero() acquires z (now 0), prints 0, releases o (now 1)
2. odd() acquires o (now 0), prints 1, releases z (now 1)
3. zero() acquires z (now 0), prints 0, releases e (now 1)
4. even() acquires e (now 0), prints 2, releases z (now 1)
5. zero() acquires z (now 0), prints 0, releases o (now 1)
6. odd() acquires o (now 0), prints 3, releases z (now 1)

Output: 010203

The semaphores act as a token-passing mechanism, ensuring only one thread can execute at a time and in the correct order. Each thread blocks on acquire() until another thread calls release() on its semaphore, creating a perfectly synchronized sequence.

Example Walkthrough

Let's trace through the execution with n = 2 to see how the semaphores coordinate the threads to produce output "0102".

Initial State:

• Semaphore z = 1 (zero thread can start)
• Semaphore e = 0 (even thread blocked)
• Semaphore o = 0 (odd thread blocked)
• Thread A will call zero() twice (i = 0, 1)
• Thread B will call even() once (i = 2)
• Thread C will call odd() once (i = 1)

Step 1: First Zero (Thread A, i=0)

• zero() calls z.acquire() → succeeds (z: 1→0)
• Prints 0
• Since i=0 is even, calls o.release() → (o: 0→1)
• Thread A blocks on next iteration waiting for z

Step 2: First Odd (Thread C, i=1)

• odd() was waiting on o.acquire() → now succeeds (o: 1→0)
• Prints 1
• Calls z.release() → (z: 0→1)
• Thread C completes (no more odd numbers)

Step 3: Second Zero (Thread A, i=1)

• zero() calls z.acquire() → succeeds (z: 1→0)
• Prints 0
• Since i=1 is odd, calls e.release() → (e: 0→1)
• Thread A completes (reached n iterations)

Step 4: First Even (Thread B, i=2)

• even() was waiting on e.acquire() → now succeeds (e: 1→0)
• Prints 2
• Calls z.release() → (z: 0→1)
• Thread B completes (no more even numbers)

Final Output: 0102

The key insight is how the semaphores create a handoff pattern:

• Zero always goes first (z starts at 1)
• Zero decides who goes next based on iteration count
• Odd/Even always hand control back to Zero
• This creates the pattern: Zero→Odd→Zero→Even, exactly as needed

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The code implements a thread synchronization mechanism where three methods (zero, even, and odd) work together to print a sequence. Analyzing each method:

• The zero method runs a loop n times, performing constant-time operations (acquire semaphore, print, release semaphore) in each iteration: O(n)
• The even method iterates through even numbers from 2 to n, which is approximately n/2 iterations with constant-time operations: O(n/2) = O(n)
• The odd method iterates through odd numbers from 1 to n, which is approximately n/2 iterations (or (n+1)/2 for odd n) with constant-time operations: O(n/2) = O(n)

Since these methods run concurrently but the total number of operations across all threads is proportional to n, the overall time complexity is O(n).

Space Complexity: O(1)

The space usage consists of:

• Three semaphore objects (z, e, o), each using constant space
• One integer variable n storing the input value
• Loop variables (i) in each method

All of these use constant space regardless of the input size n. The semaphores themselves don't grow with n - they simply maintain internal counters. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Semaphore Release Logic in Zero Thread

One of the most common mistakes is getting the logic wrong for determining which thread (odd or even) to release after printing zero. Developers often confuse the iteration index with the actual number being printed next.

Incorrect Implementation:

def zero(self, printNumber):
    for i in range(self.n):
        self.zero_semaphore.acquire()
        printNumber(0)
        # WRONG: Using the wrong condition
        if (i + 1) % 2 == 0:  # Checking if next number is even
            self.even_semaphore.release()
        else:
            self.odd_semaphore.release()

Why it's wrong: The iteration index i starts at 0, and when i=0, we want to print 1 (odd) next. The correct check is i % 2 == 0 releases odd, not (i + 1) % 2 == 1.

Solution: Remember that the iteration index corresponds to which positive number comes next:

• Index 0 → Number 1 (odd)
• Index 1 → Number 2 (even)
• Index 2 → Number 3 (odd)
• Index 3 → Number 4 (even)

2. Deadlock from Incorrect Initial Semaphore Values

Incorrect Implementation:

def __init__(self, n):
    self.n = n
    # WRONG: All semaphores initialized to 0
    self.zero_semaphore = Semaphore(0)
    self.even_semaphore = Semaphore(0)
    self.odd_semaphore = Semaphore(0)

Why it causes deadlock: If all semaphores start at 0, every thread will block on acquire() waiting for someone else to release() first. No thread can proceed, creating a circular wait condition.

Solution: Always ensure the zero semaphore starts with value 1, allowing the sequence to begin properly.

3. Range Calculation Errors in Odd/Even Threads

Incorrect Implementation:

def odd(self, printNumber):
    # WRONG: Off-by-one error or incorrect range
    for i in range(0, self.n, 2):  # Generates 0, 2, 4...
        self.odd_semaphore.acquire()
        printNumber(i + 1)  # Trying to fix it here
        self.zero_semaphore.release()

Why it's wrong: Using complex calculations or adjustments can lead to:

• Printing wrong numbers (0, 2, 4 instead of 1, 3, 5)
• Missing the last number when n is odd
• Thread executing wrong number of iterations

Solution: Use clear, explicit ranges:

• Odd: range(1, self.n + 1, 2) generates 1, 3, 5...
• Even: range(2, self.n + 1, 2) generates 2, 4, 6...

4. Missing Edge Case Handling for n=1

Potential Issue: When n=1, only the odd thread should execute once (printing "01"). The even thread's loop range(2, 2, 2) correctly produces no iterations, but developers sometimes add unnecessary special case handling that breaks the synchronization.

Incorrect "Fix":

def even(self, printNumber):
    if self.n < 2:
        return  # WRONG: Exits without proper synchronization
    for i in range(2, self.n + 1, 2):
        self.even_semaphore.acquire()
        printNumber(i)
        self.zero_semaphore.release()

Why it's wrong: The natural behavior of range(2, 2, 2) producing an empty sequence already handles this correctly. Adding early returns can disrupt the expected thread coordination.

Solution: Trust the range function to handle edge cases naturally. The empty loop body for even thread when n=1 is the correct behavior.

5. Race Condition in Thread Termination

Incorrect Assumption: Assuming threads will naturally terminate in order or that the main thread can immediately proceed after starting all threads.

Solution: When using this class, always properly join all threads:

import threading

zoo = ZeroEvenOdd(5)
threads = [
    threading.Thread(target=zoo.zero, args=(print,)),
    threading.Thread(target=zoo.odd, args=(print,)),
    threading.Thread(target=zoo.even, args=(print,))
]

for t in threads:
    t.start()

for t in threads:
    t.join()  # Essential: Wait for all threads to complete

Without proper joining, the main program might terminate before threads finish, causing incomplete output.