The problem was like this:
Given an array:
[1, 2, 1, 3, 4]
where each index value shows the production of that particular day. So, at index 0
, production is 1
, index 1
- production is 2
, so on...
Then we're given some targets (N
numbers of them). For a given target T
, we've to find the index till which the cumulative production matches the target.
For e.g., a target of 4
will be achieved by index 2
(1 + 2 + 1 = 4 >= 4). Similarly, a target of 10
will be achieved by index 4
(1 + 2 + 1 + 3 + 4 = 11 >= 10). Basically, the target is achieved for index i
, if cumulative sum till that index is greater than target
. We've find the minimum index for each target.
For the above array, sample input and output would be:
4, 2, 10
2, 1, 4
My idea for the problem is: While reading the array as input, I pre-process the array to store cumulative at each index. So, I'll convert the above array to:
[1, 3, 4, 7, 11]
and then for the given target, I'll find the minimum value in array greater than that target (can easily be done using binary search).
Assuming the total number of targets input is Q
and size of initial array is T
, my algorithm would be O(Qlog(T))
, which seems to be quite fine. But, it failed with TLE for input #5 on hackerearth.
Then I thought of maintaining a target cache (Map<Long, Integer>
), which I'll populate after reading each array element. That map will store the index of each possible target
till the maximum value.
For the above array, the map which I build would be like:
{1=0, 2=1, 3=1, 4=2, 5=3, 6=3, 7=3, 8=4, 9=4, 10=4, 11=4}
So, for each target, I can just do map.get(target)
, to get the index. For this solution, pre-processing numbers, and building map should be O(maxTarget)
, where maxTarget is the maximum value a target can get. And then fetching result is just O(1)
. But again, this also failed with TLE.
I'm completely out of thought to modify this to make the last input pass. Here's my code for 2nd approach (map):
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int T = Integer.parseInt(line);
String input = br.readLine();
StringTokenizer tokenizer = new StringTokenizer(input, " ");
long[] numbers = new long[T];
Map<Long, Integer> targetCache = new HashMap<Long, Integer>();
int i = 0;
while (tokenizer.hasMoreTokens()) {
int nextTarget = Integer.parseInt(tokenizer.nextToken());
long previousTarget = i == 0 ? 0 : numbers[i - 1];
numbers[i] = previousTarget + nextTarget;
long currentCumulativeTarget = numbers[i];
for (long j = previousTarget + 1; j <= currentCumulativeTarget; j++) {
targetCache.put(j, i);
}
i++;
}
System.out.println(targetCache);
int Q = Integer.parseInt(br.readLine());
for (int x = 0; x < Q; x++) {
long target = Long.parseLong(br.readLine());
Integer index = targetCache.get(target);
// If target can't be matched, print -1
System.out.println(index == null ? -1 : index);
}
}
How can the above solution be optimized further? Any leads? BTW, I can't test the solution, as that was the part of a interview test, and I can't see that question again.