Welcome to Subscribe On Youtube

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) 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.

 

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$, the zero 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 the even function or the odd function needs to be executed next.
  • Semaphore $e$ controls the execution of the even function. When the value of semaphore $e$ is $1$, the even 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$, the odd 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)$.

  • class ZeroEvenOdd {
        private int n;
        private Semaphore z = new Semaphore(1);
        private Semaphore e = new Semaphore(0);
        private Semaphore o = new Semaphore(0);
    
        public ZeroEvenOdd(int n) {
            this.n = n;
        }
    
        // printNumber.accept(x) outputs "x", where x is an integer.
        public void zero(IntConsumer printNumber) throws InterruptedException {
            for (int i = 0; i < n; ++i) {
                z.acquire(1);
                printNumber.accept(0);
                if (i % 2 == 0) {
                    o.release(1);
                } else {
                    e.release(1);
                }
            }
        }
    
        public void even(IntConsumer printNumber) throws InterruptedException {
            for (int i = 2; i <= n; i += 2) {
                e.acquire(1);
                printNumber.accept(i);
                z.release(1);
            }
        }
    
        public void odd(IntConsumer printNumber) throws InterruptedException {
            for (int i = 1; i <= n; i += 2) {
                o.acquire(1);
                printNumber.accept(i);
                z.release(1);
            }
        }
    }
    
  • #include <semaphore.h>
    
    class ZeroEvenOdd {
    private:
        int n;
        sem_t z, e, o;
    
    public:
        ZeroEvenOdd(int n) {
            this->n = n;
            sem_init(&z, 0, 1);
            sem_init(&e, 0, 0);
            sem_init(&o, 0, 0);
        }
    
        // printNumber(x) outputs "x", where x is an integer.
        void zero(function<void(int)> printNumber) {
            for (int i = 0; i < n; ++i) {
                sem_wait(&z);
                printNumber(0);
                if (i % 2 == 0) {
                    sem_post(&o);
                } else {
                    sem_post(&e);
                }
            }
        }
    
        void even(function<void(int)> printNumber) {
            for (int i = 2; i <= n; i += 2) {
                sem_wait(&e);
                printNumber(i);
                sem_post(&z);
            }
        }
    
        void odd(function<void(int)> printNumber) {
            for (int i = 1; i <= n; i += 2) {
                sem_wait(&o);
                printNumber(i);
                sem_post(&z);
            }
        }
    };
    
  • from threading import Semaphore
    
    
    class ZeroEvenOdd:
        def __init__(self, n):
            self.n = n
            self.z = Semaphore(1)
            self.e = Semaphore(0)
            self.o = Semaphore(0)
    
        # printNumber(x) outputs "x", where x is an integer.
        def zero(self, printNumber: 'Callable[[int], None]') -> None:
            for i in range(self.n):
                self.z.acquire()
                printNumber(0)
                if i % 2 == 0: # 'i%2==1' will have wrong answer "0201"
                    self.o.release()
                else:
                    self.e.release()
    
        def even(self, printNumber: 'Callable[[int], None]') -> None:
            for i in range(2, self.n + 1, 2):
                self.e.acquire()
                printNumber(i)
                self.z.release()
    
        def odd(self, printNumber: 'Callable[[int], None]') -> None:
            for i in range(1, self.n + 1, 2):
                self.o.acquire()
                printNumber(i)
                self.z.release()
    
    

All Problems

All Solutions