{x}
blog image

Print Zero Even Odd

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

Solution Explanation: Print Zero Even Odd

This problem requires coordinating three threads to print a sequence "010203..." in a specific order. The solution leverages semaphores for efficient thread synchronization.

Core Idea:

The solution utilizes three semaphores:

  • z: Controls the printing of zeros. Initialized to 1, allowing the zero thread to start.
  • e: Controls the printing of even numbers. Initialized to 0.
  • o: Controls the printing of odd numbers. Initialized to 0.

The flow is as follows:

  1. Zero Thread: Prints a zero. Then, based on whether the next number is even or odd, it releases either e or o, allowing the respective thread to proceed.
  2. Even Thread: Prints an even number and releases z, allowing the zero thread to run again.
  3. Odd Thread: Prints an odd number and releases z, allowing the zero thread to run again.

This creates a cycle where the zero thread always runs first, followed by either even or odd, depending on the sequence.

Time Complexity: O(n) - Each number is printed exactly once. The loop iterates through n numbers.

Space Complexity: O(1) - Constant extra space is used for semaphores, regardless of the input n.

Code Explanation (Python):

from threading import Semaphore
 
class ZeroEvenOdd:
    def __init__(self, n):
        self.n = n
        self.z = Semaphore(1)  # Initialize zero semaphore to 1
        self.e = Semaphore(0)  # Initialize even and odd semaphores to 0
        self.o = Semaphore(0)
 
    def zero(self, printNumber):
        for i in range(self.n):
            self.z.acquire()  # Acquire zero semaphore before printing 0
            printNumber(0)
            if i % 2 == 0:
                self.o.release()  # Release odd semaphore if next number is odd
            else:
                self.e.release()  # Release even semaphore if next number is even
 
    def even(self, printNumber):
        for i in range(2, self.n + 1, 2):
            self.e.acquire()  # Acquire even semaphore before printing even number
            printNumber(i)
            self.z.release()  # Release zero semaphore after printing
 
    def odd(self, printNumber):
        for i in range(1, self.n + 1, 2):
            self.o.acquire()  # Acquire odd semaphore before printing odd number
            printNumber(i)
            self.z.release()  # Release zero semaphore after printing

The Java and C++ implementations follow the same logic, using their respective semaphore mechanisms. The key is the coordinated acquisition and release of semaphores to enforce the printing order. The printNumber function is a callback provided by LeetCode's testing framework to print the numbers.

Example Usage (Conceptual):

zero_even_odd = ZeroEvenOdd(5)
 
#In a real multithreaded environment you would launch three threads, one for each function
#Here we are simulating the behavior sequentially for demonstration:
def print_number(num):
    print(num,end="")
 
zero_even_odd.zero(print_number)
zero_even_odd.odd(print_number)
zero_even_odd.even(print_number)
zero_even_odd.zero(print_number)
zero_even_odd.odd(print_number)
zero_even_odd.even(print_number)
zero_even_odd.zero(print_number)
zero_even_odd.odd(print_number)
zero_even_odd.even(print_number)
zero_even_odd.zero(print_number)
zero_even_odd.odd(print_number)
#...and so on.

This would output: 0102030405 (if run in a truly concurrent environment). The sequential execution here just demonstrates the internal logic. The semaphores ensure that even if the threads run concurrently, the output remains correctly ordered.