LeetCode Solutions Blog

Fizz Buzz Multithreaded

Number: 1316

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Implement a multithreaded version of the FizzBuzz problem where four threads are responsible for printing: "fizz", "buzz", "fizzbuzz", or the number itself. The output is based on whether the current number is divisible by 3, 5, or both, following the original FizzBuzz rules.

Key Insights

Use a shared counter to track the current number.
Employ synchronization primitives (locks, condition variables, or semaphores) to coordinate between threads.
Ensure that only the correct thread prints its value by checking divisibility conditions.
Use a loop in each thread that waits until the counter meets the thread’s specific condition.
Notify all waiting threads after each print operation to re-check their conditions.

Space and Time Complexity

Time Complexity: O(n) – each number from 1 to n is processed once. Space Complexity: O(1) – only a constant amount of extra space is used for synchronization primitives and the counter.

Solution

We use a shared counter and a synchronization mechanism to coordinate among four threads. Each thread will loop until the counter exceeds n. Inside the loop, a thread checks if the current counter satisfies its condition (divisible by 3 for fizz, 5 for buzz, both for fizzbuzz, or none for number). If the condition is met, the thread prints the corresponding output, increments the counter, and notifies other threads. If not, it waits until signaled. This ensures that only the proper thread acts for each counter update, resulting in the correct sequence of outputs.

Code Solutions

import threading

class FizzBuzz:
    def __init__(self, n):
        self.n = n                  # Total numbers to process
        self.current = 1            # Shared counter
        self.condition = threading.Condition()  # Condition variable for synchronization

    # Thread function for printing "fizz"
    def fizz(self, printFizz):
        while True:
            with self.condition:
                # Wait until current number meets the fizz condition or exceeds n
                while self.current <= self.n and (self.current % 3 != 0 or self.current % 5 == 0):
                    self.condition.wait()
                if self.current > self.n:
                    self.condition.notify_all()
                    break
                # Print fizz and move to the next number
                printFizz()
                self.current += 1
                self.condition.notify_all()

    # Thread function for printing "buzz"
    def buzz(self, printBuzz):
        while True:
            with self.condition:
                # Wait until current number meets the buzz condition or exceeds n
                while self.current <= self.n and (self.current % 5 != 0 or self.current % 3 == 0):
                    self.condition.wait()
                if self.current > self.n:
                    self.condition.notify_all()
                    break
                printBuzz()
                self.current += 1
                self.condition.notify_all()

    # Thread function for printing "fizzbuzz"
    def fizzbuzz(self, printFizzBuzz):
        while True:
            with self.condition:
                # Wait until current number meets the fizzbuzz condition or exceeds n
                while self.current <= self.n and (self.current % 3 != 0 or self.current % 5 != 0):
                    self.condition.wait()
                if self.current > self.n:
                    self.condition.notify_all()
                    break
                printFizzBuzz()
                self.current += 1
                self.condition.notify_all()

    # Thread function for printing numbers
    def number(self, printNumber):
        while True:
            with self.condition:
                # Wait until current number is not divisible by 3 or 5 or exceeds n
                while self.current <= self.n and (self.current % 3 == 0 or self.current % 5 == 0):
                    self.condition.wait()
                if self.current > self.n:
                    self.condition.notify_all()
                    break
                printNumber(self.current)
                self.current += 1
                self.condition.notify_all()