Creating new List dynamically from successive elements of another list

Question

I am working on an issue where i have an input integer list such as {0,3,6,9,12,18,21,24,27,33,39}. I need to create a new list by analyzing the original list such that if i find a sequence of multiple of 3, then first element and last element of that sequence will both be added to that list. None of the elements between the first and last element of that sequence will be added. Any other elements (without consecutive multiples of 3) will be added as such. So for an input list of {0,3,6,9,12,18,24,27,30,39,45}, my output should be [0,12,18,24,30,39,45]. Note that my first sequence of multiples of 3s was 0,3,6,9,12; so based on my requirements, the new list has 0, 12. Since 18 does not have any neighbor that differs by 3 on either side, it is added as such. Similarly, 24,27,30 are added as 24,30. Also, similar to 18, 39 and 45 are added as such. Below is my code snippet:

int difference = 3;  
public static List<Integer> parseList(List<Integer> input, int difference) {
    List<Integer> output = new ArrayList<Integer> ();
    for (int i = 0; i < input.size()-1; i++) {
        // Check if subsequent element values differ by specific difference
        if ( (input.get(i+1) - input.get(i)) == difference) {
            output.add(input.get(i));
            output.add(input.get(i+1));

        }
        else {
            output.add(input.get(i));
        }

    }
    return output;
}

My resulting output is: 0 3 3 6 6 9 9 12 12 18 24 27 27 30 30 39 Again, my expected output is: [0,12,18,24,30,39,45] Note that not only i am getting intermediate duplicate values, i am also missing last value (i.e.45).

Answer 1

As mentioned in another post, you do not get the last element of the list because your for loop terminates on the next to last element of the input list. However, if you just adjust the end condition of your for loop, you will eventually get an IndexOutOfBoundsException because your algorithm checks for i+1 on each loop.

I think it is simpler to start at index 1 and simply look backward in the array instead. From your description of the problem, I understand that you will always use the first element of the list, so we can insert it right from the start (but that means you need to make sure the input list contains at least one element):

public static List<Integer> parseList(List<Integer> input, int difference) {
    List<Integer> output = new ArrayList<Integer> ();
    if (input.size() > 0) {
        // always use first element
        int indexToAdd = -1;
        output.add(input.get(0));
        for (int i = 1; i < input.size(); i++) {
            if ( (input.get(i) - input.get(i-1)) == difference) {
                if (i == input.size()-1) {
                    output.add(input.get(i));               
                }
                else { 
                    indexToAdd = i;
                }
            }
            else {
                if(indexToAdd != -1) {
                    output.add(input.get(indexToAdd));
                    indexToAdd = -1;
                }
                output.add(input.get(i));
            }
        }
    }
    return output;
}

Answer 2

It took me a while to figure it out.... Yet, another way to code it:

ArrayList<Integer> output = new ArrayList<Integer>();

int i = 0;
while (i < input.size()) {
    int start = input.get(i);
    output.add(start);
    int end = -1;
    int x = i+1;        

    while (x < input.size()) {
        if (input.get(x++) - input.get(i++) != 3) {
            end = input.get(i-1);
            break;
        }
    }           
    if (end > 0 && end != start) {
        output.add(end);
    }
    if (start == input.get(i)) break;
}
return output;

Answer 3

The method parseList in your code is incorrect. Two issues are in this method. 1.It will add the numbers as long as adjacent numbers differ by 3. In this situation you will add duplicate numbers when consecutive differ occurs. For example, 0,3,6,9,12 Step#1. when i =0, condition 'adjacent numbers differ by 3 ' satisfiies, you add 0 and 3 to the output list. step#2 when i =1, condition 'adjacent numbers differ by 3 ' satisfiies, yop add 3 and 6 to the output list, see what? duplicate values are added. for the index i=1, you add the number to output list both in step#1 and step#2. That is why you got duplicate numbers in your output list, such as 0,3,3,6....

2. Another issue in your parseList method is that the last number is not processed, it is ignored when the last 2 numbers not differs by 3. That is why you are not able to see it in your output list either.

You can add variable to check if consecutive number differ occurs and add logic to handle the last number as well.

The following code example can help you out with this problem.

Answer 4

for (int i = 0; i < input.size()-1; i++)

This causes you to miss the last element in the list.

Therefore you should add the last element after the loop (since the last element should always appear in the output).

The following:

if ( (input.get(i+1) - input.get(i)) == difference) {
            output.add(input.get(i));
            output.add(input.get(i+1));

causes the duplicate entries, since whenever you encounter a couple of elements that differ by 3, you enter both of them.

Instead, when you discover that the difference is three, you should set some flag to true, and set it to false otherwise. As long as the flag is true, you don't put elements in the output list.

I believe something like this will do the trick:

public static List<Integer> parseList(List<Integer> input, int difference) {
    List<Integer> output = new ArrayList<Integer> ();
    boolean isSeq = false;
    for (int i = 0; i < input.size()-1; i++) {
        if ((input.get(i+1) - input.get(i)) == difference) {
            // add start of a sequence 
            if (!isSeq) {
                output.add(input.get(i));
                isSeq = true;
            }
        }
        else {
            isSeq = false;
            output.add(input.get(i));
        }

    }
    output.add(input.get(input.size()-1));
    return output;
}