Pinterest: Insert Plus or Times Between Ordered Numbers to Reach a Target, Evaluated Left to Right

Quick Overview

Decide whether placing a plus or times operator between every pair of adjacent numbers, kept in their original order, can produce a target value when the expression is evaluated strictly left to right. Tests careful handling of evaluation order, operator choices, and the size of the search space.

Insert Plus or Times Between Ordered Numbers to Reach a Target, Evaluated Left to Right

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given a list of nonnegative integers and a target. Decide whether you can place either `+` or `*` between every pair of adjacent numbers so that the resulting expression equals the target. The numbers must stay in their original order. The expression is evaluated strictly from left to right, ignoring the usual operator precedence. For example, `2 + 3 * 4` evaluates as `(2 + 3) * 4 = 20`, not `14`. ### Function Signature ```python def can_reach_target(nums: list[int], target: int) -> bool: ... ``` ### Rules - Exactly one operator, `+` or `*`, goes in each of the `len(nums) - 1` gaps. Numbers cannot be concatenated, reordered, skipped, or negated, and no parentheses can be added. - Evaluation starts with `nums[0]` as the running value. For each later index `i`, the running value becomes `running + nums[i]` or `running * nums[i]`, depending on the operator in that gap. - If `nums` has one element, there are no operators, and the answer is whether that element equals `target`. - Return `True` if at least one assignment of operators produces exactly `target`. Otherwise, return `False`. ### Constraints - `1 <= len(nums) <= 10` - `0 <= nums[i] <= 30` - `0 <= target <= 10^15` - Intermediate and final values can exceed `2^31 - 1`, but they never exceed `30^10` (about `5.9 * 10^14`), so 64-bit integers are enough. ### Examples Input: `nums = [2, 3, 4], target = 20` Output: `True` `(2 + 3) * 4 = 20`. Input: `nums = [1, 2, 3], target = 7` Output: `False` The four possible assignments give `1 + 2 + 3 = 6`, `(1 + 2) * 3 = 9`, `1 * 2 + 3 = 5`, and `1 * 2 * 3 = 6`. With standard precedence, `1 + 2 * 3` would equal `7`, but that evaluation order is not used here. Input: `nums = [5], target = 5` Output: `True`

Overview: Decide whether placing a plus or times operator between every pair of adjacent numbers, kept in their original order, can produce a target value when the expression is evaluated strictly left to right. Tests careful handling of evaluation order, operator choices, and the size of the search space.

You are given a list of nonnegative integers `nums` and an integer `target`. Decide whether you can place either `+` or `*` between every pair of adjacent numbers so that the resulting expression equals `target`. The numbers must stay in their original order. The expression is evaluated strictly from left to right, ignoring the usual operator precedence. For example, `2 + 3 * 4` evaluates as `(2 + 3) * 4 = 20`, not `14`. Rules: - Exactly one operator, `+` or `*`, goes in each of the `len(nums) - 1` gaps. Numbers cannot be concatenated, reordered, skipped, or negated, and no parentheses can be added. - Evaluation starts with `nums[0]` as the running value. For each later index `i`, the running value becomes `running + nums[i]` or `running * nums[i]`, depending on the operator in that gap. - If `nums` has one element, there are no operators, and the answer is whether that element equals `target`. - Return `True` if at least one assignment of operators produces exactly `target`. Otherwise, return `False`. The return value is a single boolean, so there is no ordering or tie-breaking choice to make. Intermediate and final values can exceed `2^31 - 1` (they never exceed `30^10 = 590490000000000`), so use 64-bit integers: `long` in Java and `long long` in C++. Example 1: Input: `nums = [2, 3, 4], target = 20` Output: `True` Explanation: `(2 + 3) * 4 = 20`. Example 2: Input: `nums = [1, 2, 3], target = 7` Output: `False` Explanation: the four assignments give `1 + 2 + 3 = 6`, `(1 + 2) * 3 = 9`, `1 * 2 + 3 = 5`, and `1 * 2 * 3 = 6`. With standard precedence, `1 + 2 * 3` would equal `7`, but that evaluation order is not used here. Example 3: Input: `nums = [5], target = 5` Output: `True` Explanation: there are no operators, and the single element equals the target.

Constraints

1 <= len(nums) <= 10
0 <= nums[i] <= 30
0 <= target <= 10^15
Exactly one operator, + or *, goes in each of the len(nums) - 1 gaps. Numbers cannot be concatenated, reordered, skipped, or negated, and no parentheses can be added.
The expression is evaluated strictly from left to right, ignoring the usual operator precedence.
Intermediate and final values can exceed 2^31 - 1, but they never exceed 30^10 (about 5.9 * 10^14), so 64-bit integers are enough (long in Java, long long in C++).

Examples

Input: ([5], 5)

Expected Output: True

Explanation: Minimum valid input: one element and no operators, and 5 equals the target.

Input: ([5], 7)

Expected Output: False

Explanation: Minimum valid input: the only reachable value is 5, which is not 7.

Hints

There are only len(nums) - 1 gaps and at most 10 numbers, so the total number of distinct operator assignments is small; you do not need a clever formula.
Because evaluation is strictly left to right, the only thing a prefix of the expression contributes to the rest of the computation is the single running value it produced.
Do not assume the running value only grows: multiplying by 0 collapses it and multiplying by 1 leaves it unchanged, so discarding a state merely because it already passed the target would lose real answers.

Approach

Because the expression is evaluated strictly left to right, a prefix of the expression is fully summarized by the single running value it produced: nothing about which operators were used matters afterwards. That gives a forward set-of-states scan.

Algorithm: start with the set {nums[0]}. For each later element value, replace the current set of running values R by { r + value : r in R } union { r * value : r in R }. After processing every element, return whether target is in the final set.

Invariant: after processing index i, the set contains exactly the values obtainable by evaluating nums[0..i] left to right under some assignment of operators to the i gaps before it. Base case: with i = 0 the only value is nums[0] (this also covers the single-element rule, where the answer reduces to nums[0] == target). Inductive step: any evaluation of nums[0..i+1] consists of an evaluation of nums[0..i] followed by exactly one operator applied with nums[i+1], and the two branches enumerate both choices; conversely every value produced by the step comes from a real prefix evaluation. So the final set is exactly the set of achievable expression values, and membership of target is the required answer.

Edge cases: a one-element list never enters the loop and correctly compares against nums[0]. Zeros matter in both directions: multiplying by 0 collapses the running value to 0, and adding 0 leaves it unchanged. Ones behave the same way (r * 1 == r while r + 1 != r). Because of that, the running value does NOT increase monotonically, so pruning states that already exceed target would be wrong -- a later multiply by 0 can bring any state back down to 0. The implementation therefore keeps every state. Values can exceed 2^31 - 1 (the maximum is 30^10 = 590490000000000), so Java uses long and C++ uses long long; all values stay below 2^53, so JavaScript numbers remain exact. Deduplicating states with a set is what keeps repeated values (e.g. many equal elements) cheap. A defensive empty-list guard returns False, though the constraints do not allow an empty list.

Time complexity:

O(2^n) -- at most 2^(n-1) distinct running values are tracked and each spawns two successors; with n = len(nums) <= 10 that is at most 512 operator assignments.

Space complexity:

O(2^n) for the set of reachable running values (at most 512 values here).