Print Zero Even Odd - Practice Coding Problems

Print Zero Even Odd - Problem

Concurrency Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 2

› Output: 0102

💡 Note: Zero thread prints 0, odd thread prints 1, zero thread prints 0, even thread prints 2. Pattern: 0→1→0→2

Example 2 — Larger Sequence

$ Input: n = 5

› Output: 0102030405

💡 Note: Complete sequence: 0→1→0→2→0→3→0→4→0→5. Total length is 2×5=10 characters.

Example 3 — Edge Case

$ Input: n = 1

› Output: 01

💡 Note: Minimum case: zero prints 0, odd prints 1. Length is 2×1=2.

Constraints

1 ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

n=3, need sequence of length 2×3=6

Thread Coordination

Zero→Odd→Zero→Even→Zero→Odd pattern

Output

Result: "010203"

Key Takeaway

🎯 Key Insight: Use semaphores to coordinate threads without busy waiting, ensuring perfect alternation

Asked in

G Google 25 M Microsoft 20 a Amazon 15 f Facebook 12

The key insight is coordinating three threads to print in alternating pattern: zero-odd-zero-even-zero-odd... Best approach uses semaphores to eliminate busy waiting and provide clean synchronization. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Semaphore-Based Synchronization	O(n)	O(1)	Use semaphores to efficiently coordinate thread execution without busy waiting
Busy Waiting with Shared Flag	O(n)	O(1)	Use a shared counter with busy waiting to coordinate thread execution

Semaphore-Based Synchronization — Algorithm Steps

Step 1: Initialize semaphores for each thread state
Step 2: Each thread acquires its semaphore before executing
Step 3: After execution, signal the appropriate next thread's semaphore

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Zero semaphore=1, others=0

Acquire

Thread acquires its semaphore before execution

Release

After execution, release next thread's semaphore

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <string.h>

typedef struct {
    int n;
    int currentNum;
    sem_t zeroSem;
    sem_t oddSem;
    sem_t evenSem;
    char* result;
    int resultIndex;
    pthread_mutex_t mutex;
} ZeroEvenOdd;

void printNumber(ZeroEvenOdd* zeo, int x) {
    pthread_mutex_lock(&zeo->mutex);
    if (x < 10) {
        zeo->result[zeo->resultIndex++] = '0' + x;
    } else {
        zeo->result[zeo->resultIndex++] = '0' + (x / 10);
        zeo->result[zeo->resultIndex++] = '0' + (x % 10);
    }
    pthread_mutex_unlock(&zeo->mutex);
}

void* zeroThread(void* arg) {
    ZeroEvenOdd* zeo = (ZeroEvenOdd*)arg;
    for (int i = 0; i < zeo->n; i++) {
        sem_wait(&zeo->zeroSem);
        printNumber(zeo, 0);
        pthread_mutex_lock(&zeo->mutex);
        if (zeo->currentNum % 2 == 1) {
            sem_post(&zeo->oddSem);
        } else {
            sem_post(&zeo->evenSem);
        }
        pthread_mutex_unlock(&zeo->mutex);
    }
    return NULL;
}

void* evenThread(void* arg) {
    ZeroEvenOdd* zeo = (ZeroEvenOdd*)arg;
    for (int i = 0; i < zeo->n / 2; i++) {
        sem_wait(&zeo->evenSem);
        pthread_mutex_lock(&zeo->mutex);
        printNumber(zeo, zeo->currentNum);
        zeo->currentNum++;
        pthread_mutex_unlock(&zeo->mutex);
        sem_post(&zeo->zeroSem);
    }
    return NULL;
}

void* oddThread(void* arg) {
    ZeroEvenOdd* zeo = (ZeroEvenOdd*)arg;
    for (int i = 0; i < (zeo->n + 1) / 2; i++) {
        sem_wait(&zeo->oddSem);
        pthread_mutex_lock(&zeo->mutex);
        printNumber(zeo, zeo->currentNum);
        zeo->currentNum++;
        pthread_mutex_unlock(&zeo->mutex);
        sem_post(&zeo->zeroSem);
    }
    return NULL;
}

char* solution(int n) {
    ZeroEvenOdd zeo;
    zeo.n = n;
    zeo.currentNum = 1;
    zeo.result = (char*)malloc((2 * n + 1) * sizeof(char));
    zeo.resultIndex = 0;
    
    sem_init(&zeo.zeroSem, 0, 1);
    sem_init(&zeo.oddSem, 0, 0);
    sem_init(&zeo.evenSem, 0, 0);
    pthread_mutex_init(&zeo.mutex, NULL);
    
    pthread_t t1, t2, t3;
    pthread_create(&t1, NULL, zeroThread, &zeo);
    pthread_create(&t2, NULL, evenThread, &zeo);
    pthread_create(&t3, NULL, oddThread, &zeo);
    
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    pthread_join(t3, NULL);
    
    zeo.result[zeo.resultIndex] = '\0';
    
    sem_destroy(&zeo.zeroSem);
    sem_destroy(&zeo.oddSem);
    sem_destroy(&zeo.evenSem);
    pthread_mutex_destroy(&zeo.mutex);
    
    return zeo.result;
}

int main() {
    int n;
    scanf("%d", &n);
    char* result = solution(n);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each thread executes n times with constant work per execution

✓ Linear Growth

Space Complexity

O(1)

Only uses semaphore objects and a few variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Semaphore-Based Synchronization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler