How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Jane Street.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Jane Street during technical interviews.

Reach a Target Using Each Number At Most Once

Company: Jane Street

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

# Reach a Target Using Each Number At Most Once You are given an array of integers `nums` and an integer `target`. Decide whether you can build an arithmetic expression that evaluates to exactly `target`, under the following rules: - Each **element** of `nums` may be used **at most once**. Elements with equal values count as separate elements. You do not have to use every element, but you must use at least one. - The numbers you pick may be arranged in any order and combined with the binary operators `+`, `-`, `*`, `/`, with any parenthesization. - Division is exact mathematical (rational) division: intermediate results may be non-integer fractions. Division by zero is not allowed at any step. - No unary minus, and no concatenating digits of different numbers (e.g. you may not glue `1` and `2` into `12`). - An expression consisting of a single picked number (no operators) is allowed, so if some element already equals `target`, the answer is `true`. Return `true` if `target` is reachable, otherwise `false`. Equality must be exact (rational arithmetic), not approximate floating-point equality. ## Examples **Example 1** ``` Input: nums = [1, 2, 3, 4], target = 24 Output: true ``` Pick `2`, `3`, `4` (leaving `1` unused): `2 * 3 * 4 = 24`. **Example 2** ``` Input: nums = [3, 3, 8, 8], target = 24 Output: true ``` `8 / (3 - 8 / 3) = 8 / (1/3) = 24`. Note the intermediate values are fractions — exact rational arithmetic matters. **Example 3** ``` Input: nums = [2, 5], target = 9 Output: false ``` All reachable values are `2`, `5`, `7`, `-3`, `3`, `10`, `2/5`, `5/2` — none equals `9`. ## Constraints - `1 <= nums.length <= 5` - `0 <= nums[i] <= 100` - `-10^4 <= target <= 10^4`

Quick Answer: This question evaluates the ability to construct arithmetic expressions from a multiset of numbers and reason about combinatorial search, operator composition, parenthesization, and exact rational arithmetic under constraints.

You are given an array of integers `nums` and an integer `target`. Decide whether you can build an arithmetic expression that evaluates to exactly `target`, under the following rules: - Each **element** of `nums` may be used **at most once**. Elements with equal values count as separate elements. You do not have to use every element, but you must use at least one. - The numbers you pick may be arranged in any order and combined with the binary operators `+`, `-`, `*`, `/`, with any parenthesization. - Division is exact mathematical (rational) division: intermediate results may be non-integer fractions. Division by zero is not allowed at any step. - No unary minus, and no concatenating digits of different numbers (e.g. you may not glue `1` and `2` into `12`). - An expression consisting of a single picked number (no operators) is allowed, so if some element already equals `target`, the answer is `true`. Return `true` if `target` is reachable, otherwise `false`. Equality must be exact (rational arithmetic), not approximate floating-point equality. **Example 1** ``` Input: nums = [1, 2, 3, 4], target = 24 Output: true ``` Pick `2`, `3`, `4` (leaving `1` unused): `2 * 3 * 4 = 24`. **Example 2** ``` Input: nums = [3, 3, 8, 8], target = 24 Output: true ``` `8 / (3 - 8 / 3) = 8 / (1/3) = 24`. Intermediate values are fractions, so exact rational arithmetic matters. **Example 3** ``` Input: nums = [2, 5], target = 9 Output: false ``` All reachable values are `2`, `5`, `7`, `-3`, `3`, `10`, `2/5`, `5/2` — none equals `9`. **Constraints** - `1 <= nums.length <= 5` - `0 <= nums[i] <= 100` - `-10^4 <= target <= 10^4`

Constraints

1 <= nums.length <= 5
0 <= nums[i] <= 100
-10^4 <= target <= 10^4
Each element may be used at most once; at least one must be used.
Operators: +, -, *, / with any parenthesization; no unary minus, no digit concatenation.
Division is exact rational division; division by zero is forbidden at every step.
Equality with target must be exact (rational), not floating-point.

Examples

Input: ([1, 2, 3, 4], 24)

Expected Output: True

Explanation: Pick 2,3,4 (leave 1 unused): 2*3*4 = 24.

Input: ([3, 3, 8, 8], 24)

Expected Output: True

Explanation: 8 / (3 - 8/3) = 8 / (1/3) = 24 — requires exact fraction arithmetic.

Hints

Do arithmetic with exact fractions (numerator/denominator reduced by gcd), never floating point — the [3,3,8,8]->24 case needs 8/3 to stay exact.
Reduce the problem: given a multiset of values, repeatedly pick any two, replace them with one of a+b, a-b, b-a, a*b, a/b, b/a (skip division when the divisor is 0), and recurse until one value remains. That value is reachable using all of them.
'At most once, at least one' means you must also try every non-empty subset of nums, not just the whole array. A single picked element counts as a valid (operator-free) expression.
Memoize on the canonical (sorted) multiset of current values to avoid recomputing the same states, and dedupe results in a set.

Quick Overview

This question evaluates the ability to construct arithmetic expressions from a multiset of numbers and reason about combinatorial search, operator composition, parenthesization, and exact rational arithmetic under constraints.