Lexicographically Smallest Negated Permutation that Sums to Target
Real-world version: Turning Numbers Over to Hit a TotalThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def lex_smallest_negated_perm(n: int, target: int) -> list[int]:public int[] lexSmallestNegatedPerm(int n, long target)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's