1116. Print Zero Even Odd
Description
You have a function printNumber
that can be called with an integer parameter and prints it to the console.
- For example, calling
printNumber(7)
prints7
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 output0
'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 numbern
that represents the numbers that should be printed.void zero(printNumber)
CallsprintNumber
to output one zero.void even(printNumber)
CallsprintNumber
to output one even number.void odd(printNumber)
CallsprintNumber
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
Solutions
Solution 1: Multithreading + Semaphore
We use three semaphores $z$, $e$, and $o$ to control the execution order of the three threads, where $z$ is initially set to $1$, and $e$ and $o$ are set to $0$.
- Semaphore $z$ controls the execution of the
zero
function. When the value of semaphore $z$ is $1$, thezero
function can be executed. After execution, the value of semaphore $z$ is set to $0$, and the value of semaphore $e$ or $o$ is set to $1$, depending on whether theeven
function or theodd
function needs to be executed next. - Semaphore $e$ controls the execution of the
even
function. When the value of semaphore $e$ is $1$, theeven
function can be executed. After execution, the value of semaphore $z$ is set to $1$, and the value of semaphore $e$ is set to $0$. - Semaphore $o$ controls the execution of the
odd
function. When the value of semaphore $o$ is $1$, theodd
function can be executed. After execution, the value of semaphore $z$ is set to $1$, and the value of semaphore $o$ is set to $0$.
The time complexity is $O(n)$, and the space complexity is $O(1)$.
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 |
|
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 |
|
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 |
|