🔄 Multithreaded FizzBuzz Problem

🧠 Problem Statement

Design a multithreaded solution to the FizzBuzz problem:

🔢 For numbers divisible by 3, print "fizz"
🔢 For numbers divisible by 5, print "buzz"
🔢 For numbers divisible by both 3 and 5, print "fizzbuzz"
🧾 For all other numbers, print the number itself

✅ Requirements

Use 4 threads:
- 🧵 Thread t1: Handles "fizz" output
- 🧵 Thread t2: Handles "buzz" output
- 🧵 Thread t3: Handles "fizzbuzz" output
- 🧵 Thread t4: Handles number output

❗ Constraints

Thread Coordination: Must use exactly 4 threads with specific responsibilities
Sequential Output: Numbers must be processed in order from 1 to n
Thread Safety: Must handle shared state safely across multiple threads
Correct Logic: Must correctly identify divisibility by 3, 5, and 15
No Deadlocks: Solution must not deadlock or starve any thread
Proper Synchronization: Must use appropriate synchronization mechanisms

📥 Input / Output

Input:

Integer n representing the upper limit
4 threads with specific responsibilities
Shared state variable for current number

Output:

Sequential output from 1 to n with appropriate fizz/buzz replacements
Correct identification of numbers divisible by 3, 5, or both

💡 Intuition About Solving This Problem

The key insight is that we need a shared counter that all threads can access, but only one thread should increment it at a time. Each thread checks if the current number matches its responsibility, and if not, it waits. When a thread processes a number, it increments the counter and notifies all other threads to check their conditions again.

🚀 Steps to Take to Solve

Design the shared state: Create a class with a shared counter variable
Implement thread coordination: Use synchronized methods with wait/notify
Define thread responsibilities: Assign specific divisibility checks to each thread
Handle synchronization: Ensure only one thread processes each number
Implement waiting logic: Make threads wait when it’s not their turn
Manage thread lifecycle: Handle completion when all numbers are processed

⚠️ Edge Cases to Consider

Thread starvation: Ensure all threads get fair access to the counter
Spurious wakeups: Use while loops to handle unexpected thread wakeups
Completion condition: Handle when all numbers have been processed
Thread interruption: Handle InterruptedException properly
Order dependency: Ensure numbers are processed in correct sequence
Divisibility logic: Handle edge cases like 0 or negative numbers

💻 Code (with comments)

Core Implementation

class MultithreadedFizzBuzz {
    private int n;           // Upper limit for the sequence
    private int num = 1;     // Current number being processed

    public MultithreadedFizzBuzz(int n) {
        this.n = n;
    }

    public synchronized void fizzbuzz() throws InterruptedException {
        while (num <= n) {
            // Check if current number is divisible by both 3 and 5
            if (num % 15 == 0) {
                System.out.println("fizzbuzz");
                num++;           // Move to next number
                notifyAll();     // Wake up all waiting threads
            } else {
                wait();          // Wait if not this thread's turn
            }
        }
    }

    public synchronized void fizz() throws InterruptedException {
        while (num <= n) {
            // Check if current number is divisible by 3 but not by 5
            if (num % 3 == 0 && num % 5 != 0) {
                System.out.println("fizz");
                num++;           // Move to next number
                notifyAll();     // Wake up all waiting threads
            } else {
                wait();          // Wait if not this thread's turn
            }
        }
    }

    public synchronized void buzz() throws InterruptedException {
        while (num <= n) {
            // Check if current number is divisible by 5 but not by 3
            if (num % 3 != 0 && num % 5 == 0) {
                System.out.println("buzz");
                num++;           // Move to next number
                notifyAll();     // Wake up all waiting threads
            } else {
                wait();          // Wait if not this thread's turn
            }
        }
    }

    public synchronized void number() throws InterruptedException {
        while (num <= n) {
            // Check if current number is not divisible by 3 or 5
            if (num % 3 != 0 && num % 5 != 0) {
                System.out.println(num);
                num++;           // Move to next number
                notifyAll();     // Wake up all waiting threads
            } else {
                wait();          // Wait if not this thread's turn
            }
        }
    }
}

Thread Class Wrapper

class FizzBuzzThread extends Thread {
    MultithreadedFizzBuzz obj;
    String method;

    public FizzBuzzThread(MultithreadedFizzBuzz obj, String method) {
        this.obj = obj;
        this.method = method;
    }

    public void run() {
        try {
            switch (method) {
                case "FizzBuzz":
                    obj.fizzbuzz();
                    break;
                case "Fizz":
                    obj.fizz();
                    break;
                case "Buzz":
                    obj.buzz();
                    break;
                case "Number":
                    obj.number();
                    break;
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

Main Method to Run

public class Main {
    public static void main(String[] args) {
        MultithreadedFizzBuzz obj = new MultithreadedFizzBuzz(15);

        Thread t1 = new FizzBuzzThread(obj, "FizzBuzz");
        Thread t2 = new FizzBuzzThread(obj, "Fizz");
        Thread t3 = new FizzBuzzThread(obj, "Buzz");
        Thread t4 = new FizzBuzzThread(obj, "Number");

        t1.start();
        t2.start();
        t3.start();
        t4.start();
    }
}

🔍 Dry Run Example

Scenario: n = 6, 4 threads running

Initial State:

num = 1
All threads are running and checking conditions

Step 1: num = 1

Thread 1 (fizzbuzz): 1 % 15 != 0 → wait()
Thread 2 (fizz): 1 % 3 != 0 → wait()
Thread 3 (buzz): 1 % 5 != 0 → wait()
Thread 4 (number): 1 % 3 != 0 && 1 % 5 != 0 → true
Thread 4 prints “1”, increments num to 2, notifies all

Step 2: num = 2

All threads wake up and check
Only Thread 4 (number) can process: 2 % 3 != 0 && 2 % 5 != 0 → true
Thread 4 prints “2”, increments num to 3, notifies all

Step 3: num = 3

All threads wake up and check
Thread 2 (fizz): 3 % 3 == 0 && 3 % 5 != 0 → true
Thread 2 prints “fizz”, increments num to 4, notifies all

Step 4: num = 4

All threads wake up and check
Only Thread 4 (number) can process: 4 % 3 != 0 && 4 % 5 != 0 → true
Thread 4 prints “4”, increments num to 5, notifies all

Step 5: num = 5

All threads wake up and check
Thread 3 (buzz): 5 % 3 != 0 && 5 % 5 == 0 → true
Thread 3 prints “buzz”, increments num to 6, notifies all

Step 6: num = 6

All threads wake up and check
Thread 2 (fizz): 6 % 3 == 0 && 6 % 5 != 0 → true
Thread 2 prints “fizz”, increments num to 7, notifies all

Result: Output: 1, 2, fizz, 4, buzz, fizz

⏱️ Time Complexity / Space Complexity

Time Complexity:

Number processing: O(n) - each number is processed once
Thread coordination: O(1) - constant time for wait/notify operations
Overall: O(n) where n is the upper limit

Space Complexity:

Shared state: O(1) - constant space for counter variables
Thread overhead: O(1) - constant space for 4 threads
Output: O(n) - space needed to store the output sequence

🧠 Insights & Tips

✅ synchronized ensures thread-safe access to shared variable num
💤 wait() blocks the thread if it’s not the correct turn
🔔 notifyAll() wakes all threads once a condition is handled
💥 Deadlocks are prevented because only one thread runs at a time and all are awakened properly

📌 Example Output (for n = 15)

1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz

🧩 Use Cases in Interviews

Practical demonstration of thread coordination
Showcases shared state handling
Allows follow-up on wait-notify vs Lock-Condition