1156MediumArrayMathTwo PointersGreedySorting

Turning Numbers Over to Hit a Total

Tracked in this browser only

Trains the technique from

LeetCode 3752Lexicographically Smallest Negated Permutation that Sums to Target

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.

The numbers 1 through n are each written down once. Any of them may be turned over, which replaces it with its negative. The numbers are then laid out in a row in whatever order you like.

Return the row whose entries total target and which comes out smallest when rows are compared entry by entry from the front. Return an empty list when no row can total target.

Examples

Example 1

Input: n = 4, target = 2
Output: [-4, 1, 2, 3]

The numbers 1 to 4 total 10, so 4 has to be turned over to bring the total down to 2. Turning the largest one over puts the smallest possible entry at the front.

Example 2

Input: n = 2, target = 0
Output: []

The numbers 1 and 2 total 3, and every turn changes the total by an even amount, so an even target can never be reached.

Example 3

Input: n = 3, target = -6
Output: [-3, -2, -1]

Every number is turned over, which is the only way to reach -6.

Constraints

1 <= n <= 10^5
-10^10 <= target <= 10^10

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 lex_smallest_negated_perm(n: int, target: int) -> list[int]:

Java

public int[] lexSmallestNegatedPerm(int n, long target)

The intended approach

Time O(n) over the numbers.Space O(n) for the row.

Turning a number over drops the total by twice that number, so with `S` the total of `1` through `n`, a row totals `target` exactly when the numbers turned over add up to `(S - target) / 2`. That has to be a whole number between nothing and `S`, which settles when a row exists at all: the target must sit within `S` either way and share `S`'s oddness or evenness. Since the numbers `1` through `n` can add up to any whole amount from nothing to `S`, nothing more is needed. For a fixed set of turned-over numbers, the smallest row is that set laid out in increasing order, which puts the turned-over numbers first, largest in size first, and then the rest rising. Choosing the set is then a greedy walk. The first entry is the negative of the largest number turned over, so that number should be as large as it can be, which means taking the largest number not exceeding what is still owed. Having fixed it, the same reasoning applies to the next entry, so walk downwards from `n` taking every number that still fits into what is owed. Because each step leaves less owing than the number just taken, the walk always finishes with nothing owing.

Pythonentry point: lex_smallest_negated_perm

def lex_smallest_negated_perm(n, target):
    total = n * (n + 1) // 2
    if target > total or target < -total:
        return []
    if (total - target) % 2 != 0:
        return []
    owed = (total - target) // 2
    turned = [False] * (n + 1)
    for v in range(n, 0, -1):
        if owed >= v:
            turned[v] = True
            owed -= v
    out = []
    for v in range(n, 0, -1):
        if turned[v]:
            out.append(-v)
    for v in range(1, n + 1):
        if not turned[v]:
            out.append(v)
    return out

The obvious version

Try every set of numbers to turn over as a bit pattern, work out the total each one gives, keep the sets that hit the target, lay each of those out in increasing order and hold on to the smallest row found. Costs two to the power of `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_lex_smallest_negated_perm(n, target):
    best = None
    for mask in range(1 << n):
        total = 0
        body = []
        for v in range(1, n + 1):
            if mask >> (v - 1) & 1:
                total -= v
                body.append(-v)
            else:
                total += v
                body.append(v)
        if total != target:
            continue
        body.sort()
        if best is None or body < best:
            best = body
    return best if best is not None else []

How this problem was checked

Reference solution executed against 15 test cases — 15 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