# LeetCode-1195. Alternate print string (multi thread)

## LeetCode Title Description

Write a program that can output a string representing this number from 1 to n, but:

• If the number can be divided by three, output "fizz".
• If the number can be divided by 5, output "buzz".
• If the number can be divided by 3 and 5 at the same time, output "fizzbuzz".

For example, when n = 15, output: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizz.

Suppose there is a class:

```class FizzBuzz {
public FizzBuzz(int n) { ... }               // constructor
public void fizz(printFizz) { ... }          // only output "fizz"
public void buzz(printBuzz) { ... }          // only output "buzz"
public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
public void number(printNumber) { ... }      // only output the numbers
}
```

• Thread A will call fizz() to determine whether it can be divided by 3. If it can, it will output fizz.
• Thread B will call buzz() to determine whether it can be divided by 5. If it can, it will output buzz.
• Thread C will call fizzbuzz() to determine whether it can be divided by 3 and 5 at the same time. If it can, it will output fizzbuzz.
• Thread D will call number() to implement a number whose output cannot be divisible by either 3 or 5.

Source: LeetCode

## Title Solution

The overall thinking is as follows:

① . the thread printing the number controls the execution of the other 3 threads. After the execution of the method printing the number of digital thread, the corresponding thread is waked up by judging the number division. But here we consider whether there is such a situation. The number method wakes up the fizz method. After the fizz method is executed, it can directly execute the buzz method. If we use the number method to transition, there will be redundant operations. (refer to Solution1)
② . each thread judges the integer division to wake up the corresponding thread. (it is more complicated to judge when releasing all permits when the program is finally considered to be stopped)
③ . use a single semaphore + for loop polling to judge. If the conditions are met, execute it. If the conditions are not met, release the permission and let other methods judge. (refer to Solution2, implementation considerations - if a method takes a long time, performance issues)

### Solution1.Semaphore + integer variable

```class FizzBuzz {
private int n;

Semaphore fizzSem = new Semaphore(0);
Semaphore buzzSem = new Semaphore(0);
Semaphore fizzBuzzSem = new Semaphore(0);
Semaphore numSem = new Semaphore(1);

private int i;

public FizzBuzz(int n) {
//Starting from 1
this.i = 1;
this.n = n;
}

// printFizz.run() outputs "fizz".
public void fizz(Runnable printFizz) throws InterruptedException {
while (true) {
fizzSem.acquire();
if (i > n) {
break;
}
printFizz.run();
i++;
numSem.release();
}
}

// printBuzz.run() outputs "buzz".
public void buzz(Runnable printBuzz) throws InterruptedException {
while (true) {
buzzSem.acquire();
if (i > n) {
break;
}
printBuzz.run();
i++;
numSem.release();
}
}

// printFizzBuzz.run() outputs "fizzbuzz".
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
while (true) {
fizzBuzzSem.acquire();
if (i > n) {
break;
}
printFizzBuzz.run();
i++;
numSem.release();
}
}

// printNumber.accept(x) outputs "x", where x is an integer.
public void number(IntConsumer printNumber) throws InterruptedException {
///It's mainly because the others are waiting after the execution here, so it will time out. At this time, just release all of them.
while (i <= n) {
numSem.acquire();
if (i % 3 == 0 && i % 5 == 0) {
fizzBuzzSem.release();
} else if (i % 3 == 0) {
fizzSem.release();
} else if (i % 5 == 0) {
buzzSem.release();
} else {
if (i <= n) {
printNumber.accept(i);
}
i++;
numSem.release();
}
}
release(); // Final release permit
}

private void release() {
fizzBuzzSem.release();
buzzSem.release();
fizzSem.release();
}
}
```

### Solution2.Semaphore + for round robin judgment

```class FizzBuzz {
private Semaphore semaphore = new Semaphore(1);
private int curNum = 1;
private int n;

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

// printFizz.run() outputs "fizz".
public void fizz(Runnable printFizz) throws InterruptedException {
for (; ; ) {
this.semaphore.acquire(1);
try {
if (this.curNum > n) {
return;
}

if ((this.curNum % 3 == 0) && (this.curNum % 5 != 0)) {
printFizz.run();
this.curNum++;
}
} finally {
// Release the permit anyway.
this.semaphore.release(1);
}
}
}

// printBuzz.run() outputs "buzz".
public void buzz(Runnable printBuzz) throws InterruptedException {
for (; ; ) {
this.semaphore.acquire(1);
try {
if (this.curNum > n) {
return;
}

if ((this.curNum % 3 != 0) && (this.curNum % 5 == 0)) {
printBuzz.run();
this.curNum++;
}
} finally {
this.semaphore.release(1);
}
}
}

// printFizzBuzz.run() outputs "fizzbuzz".
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
for (; ; ) {
this.semaphore.acquire(1);
try {
if (this.curNum > n) {
return;
}

if ((this.curNum % 3 == 0) && (this.curNum % 5 == 0)) {
printFizzBuzz.run();
this.curNum++;
}
} finally {
this.semaphore.release(1);
}
}
}

// printNumber.accept(x) outputs "x", where x is an integer.
public void number(IntConsumer printNumber) throws InterruptedException {
for (; ; ) {
this.semaphore.acquire(1);

try {
if (this.curNum > n) {
return;
}

if ((this.curNum % 3 != 0) && (this.curNum % 5 != 0)) {
printNumber.accept(this.curNum);
this.curNum++;
}
} finally {
this.semaphore.release(1);
}
}
}
}

```

## Reference resources

250 original articles published, 55 praised, 380000 visitors+

Posted on Wed, 05 Feb 2020 21:37:20 -0800 by Mackey18