1116. Print Zero Even Odd

MediumConcurrency

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 or e depending on whether the next number should be odd or even.

The odd and even functions will:

Wait to acquire o or e (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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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 the even() function.
self.o (semaphore for odd numbers): Initialized with a count of 0, will be used to control the odd() 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. If i % 2 equals 0, then the next number is odd; otherwise, it's even.
Release the semaphore self.o if the next number is odd or self.e if it's even. This will unblock the odd or even 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) where i is the current even number in the loop to print the number to the console.
Release the self.z semaphore, allowing the zero 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) where i is the current odd number in the loop to print the number to the console.
Release the self.z semaphore, allowing the zero 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsetsGenerating random numbersGenerating permutationsSorting integers

Example 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 semaphore self.z initialized to 1, so it can proceed immediately.
Thread running zero function acquires semaphore self.z (decrements self.z to 0) and prints "0".
Since the next number is 1 (odd), the thread running zero releases semaphore self.o (increments self.o to 1).
Thread running odd function was waiting for self.o to be greater than 0, so it can proceed now.
The odd thread running the odd function acquires self.o (decrements self.o to 0) and prints "1".
The odd thread then releases semaphore self.z (increments self.z to 1), enabling the zero function to print again.
The zero function's thread acquires self.z again (decrements self.z to 0) and prints the second "0".
Since the next number is 2 (even), the thread running zero now releases semaphore self.e (increments self.e to 1).
The thread running even function was waiting for self.e to be greater than 0, so it can now proceed.
The even thread acquires semaphore self.e (decrements self.e to 0) and prints "2".
Finally, the even thread releases semaphore self.z (increments self.z to 1), but since we have printed all numbers up to n, 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

Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Combinatorial problemsRandom number generationTopological sortingMatrix multiplication

I don’t know

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 called n times, since it iterates from 0 to n-1. So, its time complexity is O(n).
The even method is called n/2 times because it only deals with even numbers starting from 2 up to n. Thus, its time complexity is O(n/2), which simplifies to O(n) when analyzed for asymptotic behavior.
Similarly, the odd method is called n/2 times since it only deals with odd numbers starting from 1 to n. So, its complexity is also O(n/2), which simplifies to O(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 to n.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1116. Print Zero Even Odd

Problem Description

Intuition

Solution Approach

zero function

even function

odd function

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

`zero` function

`even` function

`odd` function