LeetCode 1116 - Print Zero Even Odd

Difficulty: 🟡 Medium
Topics: Concurrency

Solution

Problem Understanding

The problem requires us to implement a multithreaded class ZeroEvenOdd that coordinates three separate threads to print numbers in a specific sequence. Thread A prints 0s, Thread B prints even numbers, and Thread C prints odd numbers. The output must interleave zeros with increasing numbers starting from 1 up to n, producing a sequence like "010203..." of length 2n.

The input n determines the largest number in the sequence. For example, if n = 5, the sequence would be "0102030405". The constraints 1 <= n <= 1000 indicate that the sequence could be long but not so large that performance or memory would be an issue in standard concurrency control mechanisms.

Important edge cases include n = 1, where the output should be "01", and higher values like n = 1000, where thread synchronization must scale correctly. The problem guarantees that there will always be three threads and that the threads will call their respective methods asynchronously. This means a naive sequential implementation will not work; correct synchronization is critical to maintain the interleaving pattern.

Approaches

The brute-force approach would involve busy-waiting loops where each thread repeatedly checks whether it is their turn to print. While this could produce the correct output, it is highly inefficient because threads waste CPU cycles continuously checking conditions rather than blocking and waiting for the right signal.

The optimal approach is to use synchronization primitives like semaphores or locks. The key insight is that the printing order is deterministic: each zero must be followed by either an odd or even number in sequence. By controlling thread execution using semaphores, we ensure that threads only proceed when it is their turn, avoiding busy-waiting and guaranteeing correct order.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Threads busy-wait checking conditions
Optimal	O(n)	O(1)	Uses semaphores to synchronize threads efficiently

Algorithm Walkthrough

Initialize three semaphores: zero_sem starts at 1, odd_sem and even_sem start at 0. This ensures that zero prints first.
The zero thread enters a loop from 1 to n. Each iteration, it acquires zero_sem (blocking if not available), prints 0, and releases either odd_sem or even_sem depending on whether the next number is odd or even.
The odd thread loops through all odd numbers up to n. Each iteration, it acquires odd_sem, prints the number, and releases zero_sem to allow the next zero to be printed.
The even thread loops through all even numbers up to n. Each iteration, it acquires even_sem, prints the number, and releases zero_sem.
The invariant is that zero_sem is only released by odd or even after printing a number, and odd_sem or even_sem is only released by zero. This ensures strict alternation.

Why it works: At any point, only one thread is allowed to print. The semaphores enforce that zeros and numbers alternate correctly. Each number follows a zero and zeros only print when it is their turn. This guarantees the correct sequence for any n.

Python Solution

from threading import Semaphore
from typing import Callable

class ZeroEvenOdd:
    def __init__(self, n: int):
        self.n = n
        self.zero_sem = Semaphore(1)
        self.odd_sem = Semaphore(0)
        self.even_sem = Semaphore(0)
        
    def zero(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1):
            self.zero_sem.acquire()
            printNumber(0)
            if i % 2 == 1:
                self.odd_sem.release()
            else:
                self.even_sem.release()
    
    def even(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(2, self.n + 1, 2):
            self.even_sem.acquire()
            printNumber(i)
            self.zero_sem.release()
    
    def odd(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1, 2):
            self.odd_sem.acquire()
            printNumber(i)
            self.zero_sem.release()

In this implementation, the semaphores are used to block threads until it is their turn to print. zero_sem allows zero to start, and then alternates with either odd_sem or even_sem depending on the number to print. This enforces the correct interleaving sequence.

Go Solution

package main

import "sync"

type ZeroEvenOdd struct {
	n        int
	zeroSem  chan struct{}
	oddSem   chan struct{}
	evenSem  chan struct{}
}

func NewZeroEvenOdd(n int) *ZeroEvenOdd {
	return &ZeroEvenOdd{
		n:       n,
		zeroSem: make(chan struct{}, 1),
		oddSem:  make(chan struct{}, 0),
		evenSem: make(chan struct{}, 0),
	}
}

func (z *ZeroEvenOdd) Zero(printNumber func(int)) {
	for i := 1; i <= z.n; i++ {
		<-z.zeroSem
		printNumber(0)
		if i%2 == 1 {
			z.oddSem <- struct{}{}
		} else {
			z.evenSem <- struct{}{}
		}
	}
}

func (z *ZeroEvenOdd) Even(printNumber func(int)) {
	for i := 2; i <= z.n; i += 2 {
		<-z.evenSem
		printNumber(i)
		z.zeroSem <- struct{}{}
	}
}

func (z *ZeroEvenOdd) Odd(printNumber func(int)) {
	for i := 1; i <= z.n; i += 2 {
		<-z.oddSem
		printNumber(i)
		z.zeroSem <- struct{}{}
	}
}

In Go, buffered channels of size 1 act as semaphores. The zero thread starts by sending to zeroSem, then alternates releasing oddSem or evenSem depending on the number. Other threads block until the channel is available.

Worked Examples

For n = 2:

Iteration	zero_sem	odd_sem	even_sem	Output
Start	1	0	0	""
i = 1 zero	0	1	0	0
i = 1 odd	1	0	0	01
i = 2 zero	0	0	1	010
i = 2 even	1	0	0	0102

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each number is printed exactly once
Space	O(1)	Semaphores/channels use constant space regardless of n

Since the semaphores only track thread states and not the numbers themselves, space remains constant.

Test Cases

def capture_output(n):
    result = []
    def printNumber(x):
        result.append(str(x))
    return result, printNumber

# n = 1
out, printer = capture_output(1)
zeo = ZeroEvenOdd(1)
from threading import Thread
Thread(target=zeo.zero, args=(printer,)).start()
Thread(target=zeo.even, args=(printer,)).start()
Thread(target=zeo.odd, args=(printer,)).start()
import time; time.sleep(0.1)
assert "".join(out) == "01"  # basic edge case

# n = 2
out, printer = capture_output(2)
zeo = ZeroEvenOdd(2)
Thread(target=zeo.zero, args=(printer,)).start()
Thread(target=zeo.even, args=(printer,)).start()
Thread(target=zeo.odd, args=(printer,)).start()
time.sleep(0.1)
assert "".join(out) == "0102"  # example 1

# n = 5
out, printer = capture_output(5)
zeo = ZeroEvenOdd(5)
Thread(target=zeo.zero, args=(printer,)).start()
Thread(target=zeo.even, args=(printer,)).start()
Thread(target=zeo.odd, args=(printer,)).start()
time.sleep(0.1)
assert "".join(out) == "0102030405"  # example 2

# n = 1000
out, printer = capture_output(1000)
zeo = ZeroEvenOdd(1000)
Thread(target=zeo.zero, args=(printer,)).start()
Thread(target=zeo.even, args=(printer,)).start()
Thread(target=zeo.odd, args=(printer,)).start()
time.sleep(0.5)
assert "".join(out) == "".join(f"0{i}" for i in range(1,1001))  # stress test

| Test | Why |