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:
|
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 71 72 73 74 75 76 77 |
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 with X = " + sum; } } //Using sort, Time O(n^2) space O(1) private static DistanceValue findSort(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 skipped_number = input[i] + 1; skipped_number < input[i + 1]; skipped_number++) { subsum = subsum + skipped_number; minDistance = min(minDistance, new DistanceValue(subsum, target, skipped_number)); } } } return minDistance; } private static DistanceValue min(DistanceValue oldValue, DistanceValue candidate) { if (oldValue == null) { return candidate; } return candidate.compareTo(oldValue) < 0 ? candidate : oldValue; } //Use TreeSet, Time O(nlogn), Space O(n) private static DistanceValue findTreeSet(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 subsum = sum; for (int skipped_number = input[i] + 1; skipped_number < input[i + 1]; skipped_number++) { subsum = subsum + skipped_number; distances.add(new DistanceValue(subsum, target, skipped_number)); } } } return distances.first(); } public static void main(String[] args) { int[] input = { 1, 3, 5, 7, 9 }; int target = 24; System.out.println(findSort(input, target)); System.out.println(findTreeSet(input, target)); } } |
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)
