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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
import java.util.TreeSet; public class FindXSumToTarget { private static class DistanceValue implements Comparable<DistanceValue> { private int distance; private int value; private int sum; public DistanceValue(int sum, int target, int value) { this.sum = sum; this.distance = Math.abs(sum - target); this.value = value; } @Override public int compareTo(DistanceValue o) { return distance - o.distance; } @Override public String toString() { return "X = " + value + ", sum = " + sum; } } //Solution 1 comparable method, Time O(n^2) space O(1) private static DistanceValue findByComparable(int[] input, int target) { int sum = 0; DistanceValue minDistance = null; for (int i = 0; i < input.length; i++) { sum = sum + input[i]; minDistance = min(minDistance, new DistanceValue(sum, target, input[i])); if (i + 1 < input.length && input[i + 1] - input[i] > 1) { int subSum = sum; for (int skippedNum = input[i] + 1; skippedNum < input[i + 1]; skippedNum++) { subSum = subSum + skippedNum; minDistance = min(minDistance, new DistanceValue(subSum, target, skippedNum)); } } } return minDistance; } private static DistanceValue min(DistanceValue oldValue, DistanceValue candidate) { if (oldValue == null) { return candidate; } return candidate.compareTo(oldValue) < 0 ? candidate : oldValue; } //Solution 2 TreeSet, Time O(nlogn), Space O(n) private static DistanceValue findByTreeSet(int[] input, int target) { int sum = 0; TreeSet<DistanceValue> distances = new TreeSet<>(); for (int i = 0; i < input.length; i++) { sum = sum + input[i]; distances.add(new DistanceValue(sum, target, input[i])); if (i + 1 < input.length && input[i + 1] - input[i] > 1) { int sumSum = sum; for (int skippedNum = input[i] + 1; skippedNum < input[i + 1]; skippedNum++) { sumSum = sumSum + skippedNum; distances.add(new DistanceValue(sumSum, target, skippedNum)); } } } return distances.first(); } public static void main(String[] args) { int[] input = { 1, 3, 5, 7, 9 }; int target = 24; System.out.println("Solution 1 with Comparable: " + findByComparable(input, target)); System.out.println("Solution 2 with treeSet: " + findByTreeSet(input, target)); } } |
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)
