FastPrepFastPrep
Problem Brief

Closest Subsequence Sum

FULLTIMEOA
See Salesforce online assessment and hiring insights

You are given an integer array nums and an integer goal.

You want to choose a subsequence of nums such that the sum of its elements is the closest possible to goal. That is, if the sum of the subsequence's elements is sum, then you want to minimize the absolute difference abs(sum - goal).

Return the minimum possible value of abs(sum - goal).

Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array.

1Example 1

Input
nums = [5, -7, 3, 5], goal = 6
Output
0
Explanation

Choose the whole array as a subsequence, with a sum of 6. This is equal to the goal, so the absolute difference is 0.

2Example 2

Input
nums = [7, -9, 15, -2], goal = -5
Output
1
Explanation

Choose the subsequence [7, -9, -2], with a sum of -4. The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.

3Example 3

Input
nums = [1, 2, 3], goal = -7
Output
7
Explanation

No subsequence can get closer than an absolute difference of 7 from the goal.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= nums.length <= 40
  • -10^7 <= nums[i] <= 10^7
  • -10^9 <= goal <= 10^9
public int minAbsDifference(int[] nums, int goal) {
  // write your code here (You might want to refer to LC1755:)
}
Input

nums

[5, -7, 3, 5]

goal

6

Output

0

Sign in to submit your solution.