LeetCode #1116 — MEDIUM

Print Zero Even Odd

Move from brute-force thinking to an efficient approach using core interview patterns strategy.

The Problem

Problem Statement

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

Step 01

Brute Force Baseline

Problem summary: 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

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: General problem-solving

Example 1

Example 2

Core Insight

What unlocks the optimal approach

No official hints in dataset. Start from constraints and look for a monotonic or reusable state.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #1116: Print Zero Even Odd
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);
        }
    }
}

// Accepted solution for LeetCode #1116: Print Zero Even Odd
// Auto-generated Go example from java.
func exampleSolution() {
}
// Reference (java):
// // Accepted solution for LeetCode #1116: Print Zero Even Odd
// 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);
//         }
//     }
// }

# Accepted solution for LeetCode #1116: Print Zero Even Odd
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:
                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()

// Accepted solution for LeetCode #1116: Print Zero Even Odd
use std::sync::Condvar;
use std::sync::Mutex;

struct ZeroEvenOdd {
    state: (Mutex<i32>, Condvar),
    n: i32,
}

impl ZeroEvenOdd {
    fn new(n: i32) -> Self {
        let state = (Mutex::new(0), Condvar::new());
        ZeroEvenOdd { state, n }
    }

    fn zero(&self, print_number: impl Fn(i32)) {
        self.job(true, print_number, |state| {
            !(*state == 2 * self.n || *state % 2 == 0)
        });
    }

    fn odd(&self, print_number: impl Fn(i32)) {
        self.job(false, print_number, |state| {
            !(*state == 2 * self.n || *state % 2 == 1 && *state % 4 == 1)
        });
    }

    fn even(&self, print_number: impl Fn(i32)) {
        self.job(false, print_number, |state| {
            !(*state == 2 * self.n || *state % 2 == 1 && *state % 4 == 3)
        });
    }

    fn job(
        &self,
        zero: bool,
        print_number: impl Fn(i32),
        condition: impl FnMut(&mut i32) -> bool + Copy,
    ) {
        loop {
            let (lock, cvar) = &self.state;
            let mut g = cvar.wait_while(lock.lock().unwrap(), condition).unwrap();
            if *g == 2 * self.n {
                break;
            }
            print_number(if zero { 0 } else { (*g + 1) / 2 });
            *g += 1;
            cvar.notify_all();
        }
    }
}

#[test]
fn test() {
    use std::sync::mpsc::channel;
    use std::sync::Arc;
    use threadpool::ThreadPool;

    let zero_even_odd = Arc::new(ZeroEvenOdd::new(5));
    let (tx, rx) = channel();
    let pool = ThreadPool::new(4);

    for i in 0..3 {
        let zero_even_odd = zero_even_odd.clone();
        let tx = tx.clone();
        pool.execute(move || match i {
            0 => zero_even_odd.zero(|x| tx.send(x.to_string()).unwrap()),
            1 => zero_even_odd.even(|x| tx.send(x.to_string()).unwrap()),
            2 => zero_even_odd.odd(|x| tx.send(x.to_string()).unwrap()),
            _ => panic!(),
        });
    }
    pool.join();
    let nums: Vec<String> = rx.try_iter().collect();
    let res = nums.join("");
    let ans = "0102030405".to_string();
    assert_eq!(res, ans);
}

// Accepted solution for LeetCode #1116: Print Zero Even Odd
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1116: Print Zero Even Odd
// 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);
//         }
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.

OPTIMIZED

O(n) time

O(1) space

Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.

Shortcut: If you are using nested loops on an array, there is almost always an O(n) solution. Look for the right auxiliary state.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.