Data scientists at Amazon are working on a logistics optimization tool to arrange delivery routes based on existing route patterns.
A prototype algorithm takes in two integers, size and target_sum, and generates a sequence of size size whose sum of elements equals target_sum, and the absolute values of the elements form a permutation of size size. The tool outputs the lexicographically smallest such sequence.
Given two integers, size and target_sum, return the lexicographically smallest sequence of integers such that:
- The sum of its elements equals
target_sum. - The absolute values of its elements form a permutation of size
size.
Note: A sequence of size integers is a permutation if it contains the integers from 1 to size exactly once.
Given two permutations x and y, x is lexicographically smaller than y if there exists an index i where x[i] != y[i], and for this smallest index i, x[i] < y[i]. This means that when comparing x and y element by element from the start, the first position at which they differ determines their order. If the element in x is less than the corresponding element in y at this position, x is considered smaller.
Example
Suppose size = 5, target_sum = 9.
Some sequences of size 5 with target_sum = 9 are:
[-1, -2, 3, 4, 5]
[-2, -1, 3, 4, 5]
[-3, 1, 2, 4, 5]
[3, 4, 5, -2, -1]
[-3, 2, 1, 4, 5]Among these, [-3, 1, 2, 4, 5] is lexicographically smallest.
Example
Suppose size = 4, target_sum = -2.
One valid answer is:
[-4, -2, 1, 3]Complete the function findOptimalSequence in the editor below.
The function is expected to return an INTEGER_ARRAY.
The function accepts the following parameters:
INTEGER sizeLONG_INTEGER target_sum
The problem reduces to choosing which numbers from 1 to size should be negated. Let T be the sum of 1..size; if a subset sums to (T – target_sum) / 2, then negating exactly those numbers produces the required total. Feasibility requires |target_sum| <= T and T – target_sum to be even. To make the sequence lexicographically smallest, we want the earliest positions as small as possible, so the greedy subset selection should favor larger values for negation first, then output the negatives in ascending lexicographic order followed by the remaining positives. If no valid assignment exists, return an array of zeros.
