logo Practice-It logo

BJP3 Exercise 16.11: compress

Related Links:
Author: Marty Stepp (on 2013/04/01)

Write a method compress that could be added to the LinkedIntList class, that accepts an integer n representing a "compression factor" and replaces every n elements with a single element whose data value is the sum of those n nodes. Suppose a LinkedIntList variable named list stores the following values:

[2, 4, 18, 1, 30, -4, 5, 58, 21, 13, 19, 27]

If you made the call of list.compress(2);, the list would replace every two elements with a single element (2 + 4 = 6, 18 + 1 = 19, 30 + (-4) = 26, ...), storing the following elements:

[6, 19, 26, 63, 34, 46]

If you then followed this with a second call of list.compress(3);, the list would replace every three elements with a single element (6 + 19 + 26 = 51, 63 + 34 + 46 = 143), storing the following elements:

[51, 143]

If the list's size is not an even multiple of n, whatever elements are left over at the end are compressed into one node. For example, the original list on this page contains 12 elements, so if you made a call on it of list.compress(5);, the list would compress every five elements, (2 + 4 + 18 + 1 + 30 = 55, -4 + 5 + 58 + 21 + 13 = 93), with the last two leftover elements compressing into a final third element (19 + 27 = 46), resulting in the following list:

[55, 93, 46]

If n is greater than or equal to the list size, the entire list compresses into a single element. If the list is empty, the result after the call is empty regardless of what factor n is passed. You may assume that the value passed for n is >= 1.

For full credit, you may not create any new ListNode objects, though you may have as many ListNode variables as you like. For full credit, your solution must also run in O(n) time. Assume that you are adding this method to the LinkedIntList class below. You may not call any other methods of the class.

public class LinkedIntList {
    private ListNode front;   // null for an empty list
Type your solution here:

This is a partial class problem. Submit code that will become part of an existing Java class as described. You do not need to write the complete class, just the portion described in the problem.

You must log in before you can solve this problem.

Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.