Good morning. I received a comment from Dmytro regarding the post Slow Sum suggesting the use of a priority queue instead of a stream. I appreciate the comment and suggestion.
Suppose we have a list of N numbers, and repeat the following operation until we're left with only a single number: Choose any two numbers and replace them with their sum. Moreover, we associate a penalty with each operation equal to the value of the new number, and call the penalty for the entire list as the sum of the penalties of each operation. For example, given the list [1, 2, 3, 4, 5], we could choose 2 and 3 for the first operation, which would transform the list into [1, 5, 4, 5] and incur a penalty of 5. The goal in this problem is to find the worst possible penalty for a given input. Input: An array arr containing N integers, denoting the numbers in the list. Output format: An int representing the worst possible total penalty. Constraints: o 1 ≤ N ≤ 10^6 o 1 ≤ Ai ≤ 10^7, where *Ai denotes the ith initial element of an array. o The sum of values of N over all test cases will not exceed 5 * 10^6.
The description of the problem is the same as far as I can tell. I just copied it from the previous post.
1,2,3,4,5 main <<< arr: [1, 2, 3, 4, 5] main <<< output: 50 4,2,1,3 main <<< arr: [4, 2, 1, 3] main <<< output: 26
The test codes are the same. This time I did a screen capture using the implementation of the function of interest using a priority queue. The two test cases return the same values.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read input line and split values ****
String[] strs = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// **** create and populate array of integers ****
int[] arr = Arrays.stream(strs).mapToInt(Integer::parseInt).toArray();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** call function and display resuly ****
System.out.println("main <<< output: " + getTotalTime(arr));
}
Our test scaffold reads the single input line holding the values for the input array to the function of interest. The contents of the int[] array are displayed to make sure all is well so far.
The function of interest is called and the result is displayed.
/**
* Using a stream.
*
* Execution O(n log(n)) - Space: O(n)
*/
static int getTotalTime0(int[] arr) {
// **** sanity check(s) ****
if (arr.length == 1) return 0;
// ???? ????
System.out.println("<<< arr:: " + Arrays.toString(arr));
// **** sort array in descending order - O(n log(n)) ****
int[] rev = Arrays.stream(arr)
.boxed()
.sorted(Comparator.reverseOrder())
.mapToInt(Integer::intValue)
.toArray();
// ???? ????
System.out.println("<<< rev:: " + Arrays.toString(rev));
// **** initialization ****
int penalty = rev[0] + rev[1];
int penalties = penalty;
// **** loop counting penalties - O(n) ****
for (int i = 2; i < rev.length; i++) {
// **** generate penalty ****
penalty += rev[i];
// **** add penalty ****
penalties += penalty;
}
// **** return penalties ****
return penalties;
}
This is the previous implementation of the function of interest using Arrays.stream to sort the input array `arr` and generate a new int[] `rev` in which the values are sorted in monotonically descending order.
Please take a look at the comments section of the function in which the execution and space orders are listed.
/**
* Using a priority queue instead of a stream.
*
* Execution: O(n) - Space: O(n)
*/
static int getTotalTime(int[] arr) {
// **** sanity check(s) ****
if (arr.length == 1) return 0;
// **** initialization - O(n * log(n)) ****
PriorityQueue<Integer> rev = new PriorityQueue<>(arr.length, (a,b) -> b - a);
for (int i : arr) rev.add(i);
int penalty = rev.poll() + rev.poll();
int penalties = penalty;
// **** loop counting penalties - O(n) ****
while (!rev.isEmpty()) {
// **** generate penalty ****
penalty += rev.poll();
// **** add penalty ****
penalties += penalty;
}
// **** return penalties ****
return penalties;
}
This is the new implementation of the function of interest using a priority queue.
We start by performing a sanity check. There is no reason to proceed if the number of integers in the input int[] `arr` is 1.
We then initialize a priority queue with an initial capacity that matches the size of the input array and a comparator that will allow us to pull items in monotonically decreasing order. We then insert into the priority queue all the elements in the `arr`.
We then declare and initialize the `penalty` and `penalties` variables. We could have used a single variable but I used two to ease debugging by displaying variables during execution. I guess that at this point in the game I could have modified the code to use a single variable, but the code is in a different machine and I already pushed it to GitHub.
A loop is then entered. The loop will consume all the entries in the priority queue while updating the `penalties` value.
When all is said and done, our function returns the value in the `penalties` variable.
Hope you enjoyed solving this problem in a different way as suggested by Dmytro as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode). Since this problem came from a Facebook website, the number of test cases is limited. I believe in this case only two test cases were used to verify the solution.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John