1116. Print Zero Even Odd
Problem Description
In this problem, we are working with a multi-threaded setup using a class ZeroEvenOdd
. The class comes with three methods: zero
, even
, and odd
. Three different threads will call these methods. The task is to print a sequence of numbers following a pattern:
- The sequence starts with 0
- An odd number follows the 0
- Then zero again
- Then an even number ... and so on.
The sequence should follow the 010203040506...
pattern, and the total length of the sequence must be 2n
, where n
is an integer provided when creating an instance of the ZeroEvenOdd
class.
For example, if n = 5
, the sequence to print would be "0102030405".
The challenge is to ensure that:
zero()
function only outputs 0's.even()
function only outputs even numbers.odd()
function only outputs odd numbers. These functions must be called in the right sequence by different threads to maintain the mentioned sequence pattern.
Intuition
To solve this problem, we need to coordinate between threads to print the sequence in order. If the threads run without any coordination, there's no guarantee the sequence will maintain the required order because threading is non-deterministic in nature.
To ensure the correct order, we use Semaphore
objects. Semaphores are synchronization primitives that can be incremented or decremented, and threads can wait for a semaphore's value to be positive before proceeding with execution.
The key idea behind this solution is to use a semaphore z
to control the printing of zero and two other semaphores, e
for even and o
for odd numbers. Initially, since we always start with 0, semaphore z
is given an initial count of 1, and the others are set to 0, effectively blocking them.
As we proceed, the call to zero
printing function will:
- Acquire
z
. - Print 0.
- Release
o
ore
depending on whether the next number should be odd or even.
The odd
and even
functions will:
- Wait to acquire
o
ore
(respectively). - Once acquired, print the next odd or even number.
- Release
z
to allow the next zero to be printed.
This mechanism allows us to alternate between printing 0 and the next odd or even number, ensuring that the threads print numbers in the correct sequence.
Solution Approach
The solution to the problem utilizes three semaphores as a means of synchronization between threads:
self.z
(semaphore for zero): Initialized with a count of 1 because we always start the sequence with 0.self.e
(semaphore for even numbers): Initialized with a count of 0, will be used to control theeven()
function.self.o
(semaphore for odd numbers): Initialized with a count of 0, will be used to control theodd()
function.
Each function (zero
, even
, odd
) runs in its thread and follows these steps:
zero
function
The zero
function is responsible for printing zeros. It follows this loop for i
from 0 up to n-1
:
- Wait until the
self.z
semaphore is greater than 0, and then acquire it (decrement its value). - Invoke
printNumber(0)
to print zero to the console. - Determine whether the next number should be odd or even based on
i
's value. Ifi % 2
equals 0, then the next number is odd; otherwise, it's even. - Release the semaphore
self.o
if the next number is odd orself.e
if it's even. This will unblock theodd
oreven
functions, respectively.
even
function
The even
function is responsible for printing even numbers only. The loop iterates through even numbers starting from 2 until n
, incrementing by 2 in each iteration:
- Wait until the
self.e
semaphore is greater than 0, and then acquire it (decrement its value). - Invoke
printNumber(i)
wherei
is the current even number in the loop to print the number to the console. - Release the
self.z
semaphore, allowing thezero
function to print the next 0.
odd
function
Similarly, the odd
function prints odd numbers. The loop iterates through odd numbers starting from 1 until n
:
- Wait until the
self.o
semaphore is greater than 0, and then acquire it (decrement its value). - Invoke
printNumber(i)
wherei
is the current odd number in the loop to print the number to the console. - Release the
self.z
semaphore, allowing thezero
function to print the next 0.
By utilizing semaphores to control the sequence of method calls across different threads, the threads are coordinated in such a way that printNumber
prints the numbers in the sequence as if it were in a single-threaded environment.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take n = 2
as an example to illustrate how the solution approach works in practice. We want the output to be "0102." The ZeroEvenOdd
class will utilize semaphores to synchronize the print calls across the three threads corresponding to the zero
, even
, and odd
methods.
- The
zero
function has a semaphoreself.z
initialized to 1, so it can proceed immediately. - Thread running
zero
function acquires semaphoreself.z
(decrementsself.z
to 0) and prints "0". - Since the next number is 1 (odd), the thread running
zero
releases semaphoreself.o
(incrementsself.o
to 1). - Thread running
odd
function was waiting forself.o
to be greater than 0, so it can proceed now. - The
odd
thread running theodd
function acquiresself.o
(decrementsself.o
to 0) and prints "1". - The
odd
thread then releases semaphoreself.z
(incrementsself.z
to 1), enabling thezero
function to print again. - The
zero
function's thread acquiresself.z
again (decrementsself.z
to 0) and prints the second "0". - Since the next number is 2 (even), the thread running
zero
now releases semaphoreself.e
(incrementsself.e
to 1). - The thread running
even
function was waiting forself.e
to be greater than 0, so it can now proceed. - The
even
thread acquires semaphoreself.e
(decrementsself.e
to 0) and prints "2". - Finally, the
even
thread releases semaphoreself.z
(incrementsself.z
to 1), but since we have printed all numbers up ton
, the sequence is complete.
Throughout this process, the semaphores ensure that each number is printed in the correct order, and neither odd
nor even
threads print out of turn.
Solution Implementation
1from threading import Semaphore
2from typing import Callable
3
4class ZeroEvenOdd:
5 def __init__(self, n: int):
6 self.n = n
7 self.zero_semaphore = Semaphore(1) # A semaphore for allowing 'zero' to be printed
8 self.even_semaphore = Semaphore(0) # A semaphore for allowing 'even' numbers to be printed
9 self.odd_semaphore = Semaphore(0) # A semaphore for allowing 'odd' numbers to be printed
10
11 def zero(self, print_number: Callable[[int], None]) -> None:
12 """
13 Prints 'zero' n times and alternates the control between printing odd and even numbers
14 :param print_number: The function to call to print the number
15 """
16 for i in range(self.n):
17 self.zero_semaphore.acquire() # Wait for the zero semaphore to be released
18 print_number(0) # Print zero
19
20 # Determine if the next number after zero should be odd or even
21 if i % 2 == 0: # If 'i' is even, the next number should be odd
22 self.odd_semaphore.release() # Allow the odd method to print an odd number
23 else: # If 'i' is odd, the next number should be even
24 self.even_semaphore.release() # Allow the even method to print an even number
25
26 def even(self, print_number: Callable[[int], None]) -> None:
27 """
28 Prints the even numbers starting from 2 to n
29 :param print_number: The function to call to print the number
30 """
31 for i in range(2, self.n + 1, 2):
32 self.even_semaphore.acquire() # Wait for the even semaphore to be released
33 print_number(i) # Print the even number
34 self.zero_semaphore.release() # Allow the zero method to print zero again
35
36 def odd(self, print_number: Callable[[int], None]) -> None:
37 """
38 Prints the odd numbers starting from 1 to n
39 :param print_number: The function to call to print the number
40 """
41 for i in range(1, self.n + 1, 2):
42 self.odd_semaphore.acquire() # Wait for the odd semaphore to be released
43 print_number(i) # Print the odd number
44 self.zero_semaphore.release() # Allow the zero method to print zero again
45
1import java.util.concurrent.Semaphore;
2import java.util.function.IntConsumer;
3
4class ZeroEvenOdd {
5 private int n;
6 // Semaphores serve as locks to control the print order.
7 private Semaphore semaphoreZero = new Semaphore(1);
8 private Semaphore semaphoreEven = new Semaphore(0);
9 private Semaphore semaphoreOdd = new Semaphore(0);
10
11 public ZeroEvenOdd(int n) {
12 this.n = n;
13 }
14
15 /**
16 * Prints the number 0.
17 * @param printNumber The consumer interface to output a number.
18 * @throws InterruptedException if the current thread is interrupted while waiting.
19 */
20 public void zero(IntConsumer printNumber) throws InterruptedException {
21 for (int i = 1; i <= n; ++i) {
22 // Acquire the semaphore before printing 0.
23 semaphoreZero.acquire();
24 printNumber.accept(0);
25 // Determine whether to release the odd or even semaphore based on the current iteration.
26 if (i % 2 == 0) {
27 semaphoreEven.release();
28 } else {
29 semaphoreOdd.release();
30 }
31 }
32 }
33
34 /**
35 * Prints even numbers.
36 * @param printNumber The consumer interface to output a number.
37 * @throws InterruptedException if the current thread is interrupted while waiting.
38 */
39 public void even(IntConsumer printNumber) throws InterruptedException {
40 for (int i = 2; i <= n; i += 2) {
41 // Wait for the even semaphore to be released.
42 semaphoreEven.acquire();
43 printNumber.accept(i);
44 // Release the zero semaphore after printing an even number.
45 semaphoreZero.release();
46 }
47 }
48
49 /**
50 * Prints odd numbers.
51 * @param printNumber The consumer interface to output a number.
52 * @throws InterruptedException if the current thread is interrupted while waiting.
53 */
54 public void odd(IntConsumer printNumber) throws InterruptedException {
55 for (int i = 1; i <= n; i += 2) {
56 // Wait for the odd semaphore to be released.
57 semaphoreOdd.acquire();
58 printNumber.accept(i);
59 // Release the zero semaphore after printing an odd number.
60 semaphoreZero.release();
61 }
62 }
63}
64
1#include <semaphore.h>
2#include <functional> // Required for std::function
3
4class ZeroEvenOdd {
5private:
6 int n; // The maximum number we will count up to.
7 sem_t semZero, semEven, semOdd; // Semaphore for zero, even, and odd.
8
9public:
10 ZeroEvenOdd(int n) : n(n) {
11 sem_init(&semZero, 0, 1); // Initialize semZero so the first number printed is zero.
12 sem_init(&semEven, 0, 0); // Initialize semEven with no permits since we start with zero.
13 sem_init(&semOdd, 0, 0); // Initialize semOdd with no permits since we start with zero.
14 }
15
16 // Outputs "0" and alternates between even and odd permissions.
17 void zero(std::function<void(int)> printNumber) {
18 for (int i = 0; i < n; ++i) {
19 sem_wait(&semZero); // Wait for the semaphore to be available.
20 printNumber(0); // Print zero.
21 // Following zero, decide whether to allow even or odd number to print next.
22 if (i % 2 == 0) {
23 sem_post(&semOdd); // If the turn is even (starting at 0), allow odd to print next.
24 } else {
25 sem_post(&semEven); // If the turn is odd (1, 3, 5,...), allow even to print next.
26 }
27 }
28 }
29
30 // Only outputs the even numbers.
31 void even(std::function<void(int)> printNumber) {
32 for (int i = 2; i <= n; i += 2) {
33 sem_wait(&semEven); // Wait for the even semaphore to be available.
34 printNumber(i); // Print the even number.
35 sem_post(&semZero); // Signal that zero should be printed next.
36 }
37 }
38
39 // Only outputs the odd numbers.
40 void odd(std::function<void(int)> printNumber) {
41 for (int i = 1; i <= n; i += 2) {
42 sem_wait(&semOdd); // Wait for the odd semaphore to be available.
43 printNumber(i); // Print the odd number.
44 sem_post(&semZero); // Signal that zero should be printed next.
45 }
46 }
47
48 // Ensure proper destruction of semaphores to avoid any resource leak.
49 ~ZeroEvenOdd() {
50 sem_destroy(&semZero);
51 sem_destroy(&semEven);
52 sem_destroy(&semOdd);
53 }
54};
55
1const n: number = 5; // Replace with the maximum number you wish to count up to.
2let isZeroTurn = true; // Boolean to know if we should be printing 0 or switching between odd/even.
3let isOddTurn = true; // Boolean to determine whose turn it is, odd or even, after zero.
4
5// Define the printNumber function, which is a stand-in for actually printing a number.
6const printNumber = (num: number) => {
7 console.log(num);
8};
9
10// For zero printing function.
11const zero = async () => {
12 for (let i = 0; i < n; ++i) {
13 // Check if it's zero's turn before printing zero.
14 while (!isZeroTurn) await new Promise(resolve => setTimeout(resolve, 10));
15 printNumber(0);
16 // Toggle the turn to odd or even after printing 0.
17 isOddTurn = i % 2 === 0;
18 isZeroTurn = false; // Now it's not Zero's turn anymore.
19 }
20};
21
22// For even numbers printing function.
23const even = async () => {
24 for (let i = 2; i <= n; i += 2) {
25 // Wait for even's turn.
26 while (isZeroTurn || isOddTurn) await new Promise(resolve => setTimeout(resolve, 10));
27 printNumber(i);
28 isZeroTurn = true; // After printing an even number, it's now Zero's turn.
29 }
30};
31
32// For odd numbers printing function.
33const odd = async () => {
34 for (let i = 1; i <= n; i += 2) {
35 // Wait for odd's turn.
36 while (isZeroTurn || !isOddTurn) await new Promise(resolve => setTimeout(resolve, 10));
37 printNumber(i);
38 isZeroTurn = true; // After printing an odd number, it's now Zero's turn.
39 }
40};
41
42// Run the functions asynchronously to simulate parallel execution.
43zero();
44even();
45odd();
46
Time and Space Complexity
Time Complexity
The time complexity of the given code is primarily dictated by the number of iterations each method will execute:
- The
zero
method is calledn
times, since it iterates from 0 ton-1
. So, its time complexity isO(n)
. - The
even
method is calledn/2
times because it only deals with even numbers starting from 2 up ton
. Thus, its time complexity isO(n/2)
, which simplifies toO(n)
when analyzed for asymptotic behavior. - Similarly, the
odd
method is calledn/2
times since it only deals with odd numbers starting from 1 ton
. So, its complexity is alsoO(n/2)
, which simplifies toO(n)
.
All methods are executed concurrently, but since they depend on each other through the use of semaphores (synchronization mechanisms), the overall time complexity is still O(n)
, because they don't run entirely in parallel due to the synchronization constraints.
Space Complexity
The space complexity of the code is defined by the variables and synchronization primitives used:
- Three semaphores are initiated, regardless of the value of
n
. - The variable
self.n
represents the input parameter and does not change with respect ton
.
Hence, the space complexity of the class and its methods is O(1)
since the amount of space used does not scale with the input size n
.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time