How to Answer: Return the consecutive numbers.
Advice and answer examples written specifically for a Java Intermediate Level Greedy job interview.
3. Return the consecutive numbers.
This question focuses on Java array generators.
You are given an array of integer generators. You can select some of the integers from the array (possibly none or all), and add them up to "generate†a new integer. Your task is to count and return the number of consecutive integers that you can “generate†from the array generators starting from and including 0.
/*Example*/
Given generators = [1, 3]
Expected output: 2
Explanation: You can generate two consecutive integers viz. 0 and 1.
Given generators = [1, 1, 1, 4]
Expected output: 8
Explanation: You can generate the following consecutive integers:-
[] -> 0
[1] -> 1
[1, 1] -> 2
[1, 1, 1] -> 3
[4] -> 4
[1, 4] -> 5
[1, 1, 4] -> 6
[1, 1, 1, 4] -> 7
Thus you can generate eight consecutive integers from 0 to 1.Solution:
Let x1, x2, …, xk be the k integers from the given array generators. We call such one integer a “generatorâ€. Let’s assume using these k integers (k generators), we can generate consecutive integers from 0 to a. That is, we have ways to generate the following consecutive integers:
0 1 2 … a - 2 a - 1 a
Now let’s use one more generator other than the mentioned k generators and we wish to generate a new integer (a + 1). We can do it following ways:
if we have one more generator gen = 1 in generators, we can generate (a + 1) using gen = 1 and already generated integer (a),
or if we have one more generator gen = 2 in generators, we can generate (a + 1) using gen = 2 and already generated integer (a - 1),
or if we have one more generator gen = 3 in generators, we can generate (a + 1) using gen = 3 and already generated integer (a - 2),
…
…
or if we have one more generator gen = (a - 1) in generators, we can generate (a + 1) using gen = (a - 1) and already generated integer (2),
or if we have one more generator gen = a in generators, we can generate (a + 1) using gen = a and already generated integer (1),
or if we have one more generator gen = (a + 1) in generators, we can generate (a + 1) by selecting only one number from generators, gen = (a + 1).
Thus, to generate (a + 1), we require one more generator gen with condition 1 <= gen <= (a + 1). When we have such a generator, we can always generate more integers from (a + 1) to (a + gen), or we can say that we can generate all integers from 0 to (a + gen) using generators x1, x2, …, xk and gen.
If we can generate integers from 0 to a, and we can not find such gen, that is, the next-gen is either 0 or gen > a + 1, then we can not generate the consecutive integers further. So our answer will be a + 1 (we can generate a + 1 number of integers from 0 to a).
class Solution {
public int getMaximumConsecutive(int[] generators) {
Arrays.sort(generators);
int currSum = 0;
for (int gen : generators) {
if (gen > currSum + 1) break;
currSum += gen;
}
return currSum + 1;
}
}Time complexity- O(n logn)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021