0237HardMathRecursion

Nozzle Firing Book

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A calibration rig drives n nozzles, numbered 1 through n. Its test book holds every firing order of those nozzles exactly once, one order per line, each written as the nozzle numbers run together with nothing between them.

Every line of the book has the same number of digits, and the book is sorted by reading each line as a number and placing smaller numbers earlier. With n = 3 the book runs 123, then 132, then 213, then 231, then 312, and finally 321.

Given n and a line number k, with the opening line counted as line 1, return that line of the book as a string.

Examples

Example 1

Input: n = 4, k = 7
Output: "2134"

Line 7 of the four-nozzle book reads 2134, which fires each of the nozzles 1, 2, 3 and 4 once.

Example 2

Input: n = 5, k = 13
Output: "14235"

Line 13 of the five-nozzle book reads 14235, and every nozzle from 1 to 5 appears in it exactly once.

Example 3

Input: n = 1, k = 1
Output: "1"

One nozzle admits one firing order, so the book has the single line 1.

Constraints

1 <= n <= 9
1 <= k <= n!

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def firing_order(n: int, k: int) -> str:

Java

public String firingOrder(int n, int k)

The intended approach

Time O(n^2), since removing the chosen nozzle from the unused list costs O(n)Space O(n) for the unused list and the line being built

Fill the line one place at a time, keeping the still-unused nozzle numbers in ascending order. With `places` slots left to fill after the current one, the lines agreeing with the current prefix fall into groups of `places!`, so dividing the remaining offset by `places!` gives the position of the nozzle to take out of the unused list and the remainder carries into the next place. Shifting `k` down by one first turns the line number into that offset.

Pythonentry point: firing_order

def firing_order(n, k):
    from math import factorial
    unused = [str(d) for d in range(1, n + 1)]
    left = k - 1
    line = []
    for places in range(n - 1, -1, -1):
        block = factorial(places)
        index = left // block
        left -= index * block
        line.append(unused.pop(index))
    return "".join(line)

The obvious version

Generate the firing orders in ascending order and walk to the k-th one. O(k * n).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_firing_order(n, k):
    from itertools import islice, permutations
    digits = "".join(str(d) for d in range(1, n + 1))
    return "".join(next(islice(permutations(digits), k - 1, k)))

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in