Problem

You have the four functions:

  • printFizz that prints the word "fizz" to the console,
  • printBuzz that prints the word "buzz" to the console,
  • printFizzBuzz that prints the word "fizzbuzz" to the console, and
  • printNumber that prints a given integer to the console.

You are given an instance of the class FizzBuzz that has four functions: fizz, buzz, fizzbuzz and number. The same instance of FizzBuzz will be passed to four different threads:

  • Thread A: calls fizz() that should output the word "fizz".
  • Thread B: calls buzz() that should output the word "buzz".
  • Thread C: calls fizzbuzz() that should output the word "fizzbuzz".
  • Thread D: calls number() that should only output the integers.

Modify the given class to output the series [1, 2, "fizz", 4, "buzz", ...] where the ith token (1-indexed) of the series is:

  • "fizzbuzz" if i is divisible by 3 and 5,
  • "fizz" if i is divisible by 3 and not 5,
  • "buzz" if i is divisible by 5 and not 3, or
  • i if i is not divisible by 3 or 5.

Implement the FizzBuzz class:

  • FizzBuzz(int n) Initializes the object with the number n that represents the length of the sequence that should be printed.
  • void fizz(printFizz) Calls printFizz to output "fizz".
  • void buzz(printBuzz) Calls printBuzz to output "buzz".
  • void fizzbuzz(printFizzBuzz) Calls printFizzBuzz to output "fizzbuzz".
  • void number(printNumber) Calls printnumber to output the numbers.

Examples

Example 1

1
2

Input: n = 15
Output: [1,2,"fizz",4,"buzz","fizz",7,8,"fizz","buzz",11,"fizz",13,14,"fizzbuzz"]

Example 2

1
2

Input: n = 5
Output: [1,2,"fizz",4,"buzz"]

Constraints

  • 1 <= n <= 50

Solution

Method 1 – Synchronization with Semaphores/Locks

Intuition

We need to coordinate four threads so that each prints the correct value in order. We use synchronization primitives (semaphores, locks, or condition variables) to ensure only the correct thread prints at each step.

Approach

  1. Use a shared counter to track the current number.
  2. Use synchronization (semaphores, locks, or condition variables) to ensure only the correct thread prints for each number.
  3. Each thread waits for its turn, prints if the condition matches, and notifies others.
  4. Repeat until n is reached.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <functional>
#include <mutex>
#include <condition_variable>
class FizzBuzz {
    int n, curr = 1;
    std::mutex mtx;
    std::condition_variable cv;
public:
    FizzBuzz(int n) : n(n) {}
    void fizz(function<void()> printFizz) {
        while (true) {
            std::unique_lock<std::mutex> lk(mtx);
            cv.wait(lk, [&]{ return curr > n || (curr % 3 == 0 && curr % 5 != 0); });
            if (curr > n) break;
            printFizz();
            curr++;
            cv.notify_all();
        }
    }
    void buzz(function<void()> printBuzz) {
        while (true) {
            std::unique_lock<std::mutex> lk(mtx);
            cv.wait(lk, [&]{ return curr > n || (curr % 5 == 0 && curr % 3 != 0); });
            if (curr > n) break;
            printBuzz();
            curr++;
            cv.notify_all();
        }
    }
    void fizzbuzz(function<void()> printFizzBuzz) {
        while (true) {
            std::unique_lock<std::mutex> lk(mtx);
            cv.wait(lk, [&]{ return curr > n || (curr % 15 == 0); });
            if (curr > n) break;
            printFizzBuzz();
            curr++;
            cv.notify_all();
        }
    }
    void number(function<void(int)> printNumber) {
        while (true) {
            std::unique_lock<std::mutex> lk(mtx);
            cv.wait(lk, [&]{ return curr > n || (curr % 3 != 0 && curr % 5 != 0); });
            if (curr > n) break;
            printNumber(curr);
            curr++;
            cv.notify_all();
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.util.concurrent.Semaphore;
class FizzBuzz {
    private int n, curr = 1;
    private final Semaphore fizz = new Semaphore(0), buzz = new Semaphore(0), fizzbuzz = new Semaphore(0), number = new Semaphore(1);
    public FizzBuzz(int n) { this.n = n; }
    public void fizz(Runnable printFizz) throws InterruptedException {
        while (true) {
            fizz.acquire();
            if (curr > n) break;
            printFizz.run();
            curr++;
            releaseNext();
        }
    }
    public void buzz(Runnable printBuzz) throws InterruptedException {
        while (true) {
            buzz.acquire();
            if (curr > n) break;
            printBuzz.run();
            curr++;
            releaseNext();
        }
    }
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        while (true) {
            fizzbuzz.acquire();
            if (curr > n) break;
            printFizzBuzz.run();
            curr++;
            releaseNext();
        }
    }
    public void number(IntConsumer printNumber) throws InterruptedException {
        while (true) {
            number.acquire();
            if (curr > n) break;
            printNumber.accept(curr);
            curr++;
            releaseNext();
        }
    }
    private void releaseNext() {
        if (curr > n) {
            fizz.release(); buzz.release(); fizzbuzz.release(); number.release();
        } else if (curr % 15 == 0) fizzbuzz.release();
        else if (curr % 3 == 0) fizz.release();
        else if (curr % 5 == 0) buzz.release();
        else number.release();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

from threading import Lock, Condition
class FizzBuzz:
    def __init__(self, n: int):
        self.n = n
        self.curr = 1
        self.lock = Lock()
        self.cv = Condition(self.lock)
    def fizz(self, printFizz):
        while True:
            with self.cv:
                while self.curr <= self.n and (self.curr % 3 != 0 or self.curr % 5 == 0):
                    self.cv.wait()
                if self.curr > self.n:
                    self.cv.notify_all()
                    break
                printFizz()
                self.curr += 1
                self.cv.notify_all()
    def buzz(self, printBuzz):
        while True:
            with self.cv:
                while self.curr <= self.n and (self.curr % 5 != 0 or self.curr % 3 == 0):
                    self.cv.wait()
                if self.curr > self.n:
                    self.cv.notify_all()
                    break
                printBuzz()
                self.curr += 1
                self.cv.notify_all()
    def fizzbuzz(self, printFizzBuzz):
        while True:
            with self.cv:
                while self.curr <= self.n and (self.curr % 15 != 0):
                    self.cv.wait()
                if self.curr > self.n:
                    self.cv.notify_all()
                    break
                printFizzBuzz()
                self.curr += 1
                self.cv.notify_all()
    def number(self, printNumber):
        while True:
            with self.cv:
                while self.curr <= self.n and (self.curr % 3 == 0 or self.curr % 5 == 0):
                    self.cv.wait()
                if self.curr > self.n:
                    self.cv.notify_all()
                    break
                printNumber(self.curr)
                self.curr += 1
                self.cv.notify_all()

Complexity

  • ⏰ Time complexity: O(n), each number is printed once.
  • 🧺 Space complexity: O(1), only a few variables and synchronization primitives are used.