Slow Sum

I am tired. It has been a long week. I got lots of stuff done. It is already dark. The good thing is that today is December 11. On December 21 winter starts. That is only ten days away. After December 21 the days start getting longer in the northern hemisphere!!!

Just to push a little and get one more problem in before the end of the workweek, I decided to work on Slow Sum. This is just one problem in a set of about a couple dozen in the Facebook web site.

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 idea is to sum the numbers in the array two at a time replacing them by their sum. The sum is known as a penalty. Each time you get a penalty you add it to a total. The idea is to get the highest possible penalty.

It seems that a good approach would be to sort the numbers in descending order and add them from top to bottom.

int getTotalTime(int[] arr){
}

The signature for the function we need to solve is reasonable.

I will be solving this problem using Java on a Windows 10 machine using the VSCode IDE. Because I am using my machine, I will need to generate a test scaffolding to read the input data, generate an integer array, call the function in questions and display the returned results.

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 problem has two examples. The site also provides two test cases. My confidence in a good solution is not as high as if we would be submitting our code to a few dozen test cases. Such is life.

    /**
     * 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));
    }

Not going to go into too much detail. We read the input line. We generate an array of integers. Pass the array to the function / method of interest and display the results.

    /**
     * Execution O(n log(n))
     */
    static int getTotalTime(int[] arr) {

        // **** sanity check(s) ****
        if (arr.length == 1)
            return 0;

        // **** sort array in descending order O(n log(n)) ****
        int[] rev = Arrays.stream(arr)
                        .boxed()
                        .sorted(Comparator.reverseOrder())
                        .mapToInt(Integer::intValue)
                        .toArray();

        // **** 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;
    }

We start by performing some sanity checks. That avoids loading and execution code for which we may easily infer the results; so why bother.

We need to sort the elements in the array in descending order. The array is of type int[] so we are not able to sort the array in descending order with a comparator because it expects an object, in this case it would be Integer but we have an array of int.

We can create a stream, box the contents so they are upgraded to Integer, sort using a comparator, may the Integer to int and then collect the results in an array of int. Streams in Java are cool.

We then initialize our first penalty and also add it to the running total for penalties.

Now we are ready to loop through the rest of the array entries. We compute the penalty and then add it to the penalties.

When done we return the penalties.

The results match the two sample and two test cases. That said; if you discover an issue with this solution; please let me know. I will address it as soon as possible.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 4,996 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

Regards;

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.