Find possible number not in array sum to target

In array, there are frequently asked questions “Two sum”, “three sum”, “find subarray with given sum”. Here is a target sum problem with a twist – find a number not in the array, but can make subarray sum equals to or close to the target. To solve “Find a number not in array”, we will use “find negative space”. We will use the complement of array elements, and sorting techniques.

Amazon Interview Question:
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 a given input array, they are:
[1 (2) 3 (4) 5 (6) 7 (8) 9]. The skipped numbers or the numbers are not in the array are those in parentheses. They are the candidates we are looking for. We iterate over these skipped numbers, and calculate the array sum, compare it with the target sum. Then we can decide which one can make the sum equal or closest to the target sum.

A variable distance is used to to keep track the distance between the target sum and the array sum with a skipped number. In order to get the smallest distance, there are two ways to sort, comparable method or TreeSet. Considering there might be multiple numbers in a gap, e.g. [1 2 4 9 11] -> [1 2 (3) 4 (5 6 7 8) 9 (10 11) 12], we add an inner loop to check each number in the gap.

Java Code:

Output:
Solution 1 with Comparable: X = 8, sum = 24
Solution 2 with treeSet: X = 8, sum = 24

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

Download FindXSumToTarget.java
Java coding interview pocket book (2nd edition)
Java coding interview series (YouTube)

Comments are closed