Problem

You have a function printNumber that can be called with an integer parameter and prints it to the console.

  • For example, calling printNumber(7) prints 7 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 output 0’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 number n that represents the numbers that should be printed.
  • void zero(printNumber) Calls printNumber to output one zero.
  • void even(printNumber) Calls printNumber to output one even number.
  • void odd(printNumber) Calls printNumber to output one odd number.

Examples

Example 1:

1
2
3
4
5

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:

1
2

Input: n = 5
Output: "0102030405"

Class Given:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class ZeroEvenOdd {
    private int n;
    
    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        
    }
}

Solution

Method 1 - Using Semaphore

Intuition

We use three semaphores to strictly control the order of execution between the three threads. The zero thread starts, prints 0, and then signals either the odd or even thread. After printing, the odd/even thread signals the zero thread to continue.

Approach

  1. Initialize three semaphores: one for zero (starting with 1 permit), one for odd (starting with 0), one for even (starting with 0).
  2. In the zero thread, acquire its semaphore, print 0, then release the odd or even semaphore based on the index.
  3. In the odd/even thread, acquire its semaphore, print the number, then release the zero semaphore.
  4. Repeat for n cycles.

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

import java.util.concurrent.Semaphore;
import java.util.function.IntConsumer;

class ZeroEvenOddSemaphore {
    private int n;
    private final Semaphore zeroSem = new Semaphore(1);
    private final Semaphore oddSem = new Semaphore(0);
    private final Semaphore evenSem = new Semaphore(0);

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

    public void zero(IntConsumer printNumber) throws InterruptedException {
        for (int i = 0; i < n; ++i) {
            zeroSem.acquire();
            printNumber.accept(0);
            if (i % 2 == 0) {
                oddSem.release();
            } else {
                evenSem.release();
            }
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        for (int i = 2; i <= n; i += 2) {
            evenSem.acquire();
            printNumber.accept(i);
            zeroSem.release();
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i += 2) {
            oddSem.acquire();
            printNumber.accept(i);
            zeroSem.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

import java.util.concurrent.Semaphore

class ZeroEvenOddSemaphore(private val n: Int) {
    private val zeroSem = Semaphore(1)
    private val oddSem = Semaphore(0)
    private val evenSem = Semaphore(0)

    fun zero(printNumber: (Int) -> Unit) {
        for (i in 0 until n) {
            zeroSem.acquire()
            printNumber(0)
            if (i % 2 == 0) {
                oddSem.release()
            } else {
                evenSem.release()
            }
        }
    }

    fun even(printNumber: (Int) -> Unit) {
        for (i in 2..n step 2) {
            evenSem.acquire()
            printNumber(i)
            zeroSem.release()
        }
    }

    fun odd(printNumber: (Int) -> Unit) {
        for (i in 1..n step 2) {
            oddSem.acquire()
            printNumber(i)
            zeroSem.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

import threading

class ZeroEvenOddSemaphore:
    def __init__(self, n: int):
        self.n = n
        self.zeroSem = threading.Semaphore(1)
        self.oddSem = threading.Semaphore(0)
        self.evenSem = threading.Semaphore(0)

    def zero(self, printNumber):
        for i in range(self.n):
            self.zeroSem.acquire()
            printNumber(0)
            if i % 2 == 0:
                self.oddSem.release()
            else:
                self.evenSem.release()

    def even(self, printNumber):
        for i in range(2, self.n + 1, 2):
            self.evenSem.acquire()
            printNumber(i)
            self.zeroSem.release()

    def odd(self, printNumber):
        for i in range(1, self.n + 1, 2):
            self.oddSem.acquire()
            printNumber(i)
            self.zeroSem.release()

Complexity

  • ⏰ Time complexity: O(n) — Each thread prints n times, and each print is O(1).
  • 🧺 Space complexity: O(1) — Only a few semaphore objects are used for synchronization.

Method 2 - Using Synchronization (Monitor Wait/Notify)

Intuition

We use a shared state variable and synchronized methods to coordinate the three threads. Each thread waits for its turn using wait() and notifies the others using notifyAll() after printing.

Approach

  1. Use a shared integer variable (sem): 0 for zero’s turn, 1 for odd’s turn, 2 for even’s turn.
  2. In each thread, loop and use a while loop to wait until sem matches the thread’s turn.
  3. When it’s the thread’s turn, print and update sem to the next expected value, then call notifyAll().
  4. Repeat until all numbers are printed.

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

import java.util.function.IntConsumer;

class ZeroEvenOddSync {
    private int n;
    private int sem = 0;

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

    public synchronized void zero(IntConsumer printNumber) throws InterruptedException {
        for (int i = 0; i < n; ++i) {
            while (sem != 0)
                wait();
            printNumber.accept(0);
            sem = i % 2 == 0 ? 1 : 2;
            notifyAll();
        }
    }

    public synchronized void even(IntConsumer printNumber) throws InterruptedException {
        for (int i = 2; i <= n; i += 2) {
            while (sem != 2)
                wait();
            printNumber.accept(i);
            sem = 0;
            notifyAll();
        }
    }

    public synchronized void odd(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i += 2) {
            while (sem != 1)
                wait();
            printNumber.accept(i);
            sem = 0;
            notifyAll();
        }
    }
}
 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

class ZeroEvenOddSync(private val n: Int) {
    private var sem = 0

    @Synchronized
    fun zero(printNumber: (Int) -> Unit) {
        for (i in 0 until n) {
            while (sem != 0) {
                (this as java.lang.Object).wait()
            }
            printNumber(0)
            sem = if (i % 2 == 0) 1 else 2
            (this as java.lang.Object).notifyAll()
        }
    }

    @Synchronized
    fun even(printNumber: (Int) -> Unit) {
        for (i in 2..n step 2) {
            while (sem != 2) {
                (this as java.lang.Object).wait()
            }
            printNumber(i)
            sem = 0
            (this as java.lang.Object).notifyAll()
        }
    }

    @Synchronized
    fun odd(printNumber: (Int) -> Unit) {
        for (i in 1..n step 2) {
            while (sem != 1) {
                (this as java.lang.Object).wait()
            }
            printNumber(i)
            sem = 0
            (this as java.lang.Object).notifyAll()
        }
    }
}
 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

import threading

class ZeroEvenOddSync:
    def __init__(self, n: int):
        self.n = n
        self.sem = 0
        self.lock = threading.Condition()

    def zero(self, printNumber):
        for i in range(self.n):
            with self.lock:
                while self.sem != 0:
                    self.lock.wait()
                printNumber(0)
                self.sem = 1 if i % 2 == 0 else 2
                self.lock.notify_all()

    def even(self, printNumber):
        for i in range(2, self.n + 1, 2):
            with self.lock:
                while self.sem != 2:
                    self.lock.wait()
                printNumber(i)
                self.sem = 0
                self.lock.notify_all()

    def odd(self, printNumber):
        for i in range(1, self.n + 1, 2):
            with self.lock:
                while self.sem != 1:
                    self.lock.wait()
                printNumber(i)
                self.sem = 0
                self.lock.notify_all()

Complexity

  • ⏰ Time complexity: O(n) — Each thread prints n times, and each print is O(1).
  • 🧺 Space complexity: O(1) — Only a few variables and lock objects are used for synchronization.