Find X sum to target – Code

In array, there are frequently asked questions “Two sum”, “three sum”, “find subarry with given sum”. Here is a twist question, find a number X Not in the array, but can make subarray sum equals to or close to the target. To solve “Find X sum to target”, we will use “find negative space” we used in Find random number not in array, ie finding the complement of array elements, and sorting technique (or sorted data structure, such as TreeSet).

Amazon Interview Question (CareerCup):
Given an array, find an x such that all numbers less than x are equal to themselves. Numbers greater than it are equal to x, and all numbers add up to a target.
For example, [1 3 5 7 9] target = 24, answer is 8. Because when x = 8, the array has only 9 > 8, so 1+3+5+7+8 = 24 is the closest to the target.

Approach:
First we need to find out all possible numbers that match the conditions. For given input array, they are:
[1 (2) 3 (4) 5 (6) 7 (8) 9]. We can iterate over skipped numbers, [1 (2) 3 (4) 5 (6) 7 (8) 9], they are marked in braces. we can find an item that has closest sum to target by using variable Distance to keep track. Sorting or TreeSet is used to get the smallest. Because array could contain bigger gaps, e.g. [1 2 4 9 11] -> [1 2 (3) 4 (5 6 7 8) 9 (10 11) 12], we need to add another loop.

Java Code:

O Notation:
Using Sort: Time complexity: O(n^2), Space O(1)
Using TreeSet: Time complexity: O(nlogn), Space O(n)

Java coding interview pocket book (2nd edition)
Java coding interview series (YouTube)

Comments are closed