Avoid CPU time limit exceeded (core dumped) or Terminated due to timeout

[thegreymatter]

Hi recently while trying to solve a core Java algorithm question I got trapped into a problem.

Let me explain the puzzle.

There is a series of numbers. where difference between any consecutive
numbers is either a or b. The 1st number of the series is 0. Our code
should compute the last possible numbers given the total count of
elements say n and values of a and b. Constraints: 1 ≤ n, a, b ≤ 1000

Test Case 1.

stdin:

 n=3 
 a=1
 b=2

stdout:

2 3 4 

Explanation

All possible series for first test case are given below.

0,1,2
0,1,3
0,2,3
0,2,4

Hence the answer 2 3 4.

Test Case 2.

stdin:

n = 4
a = 10
b = 100

stdout:

30 120 210 300 

Series with different number of final step for second test cases are

0, 10, 20, 30
0, 10, 20, 120
0, 10, 110, 120
0, 10, 110, 210
0, 100, 110, 120
0, 100, 110, 210
0, 100, 200, 210
0, 100, 200, 300

hence the answer 30 120 210 300

Now the actual bugger. My code computes desired output for less value of n. But when n exceeds say 50 I get

CPU time limit exceeded (core dumped)
Terminated due to timeout

Kindly share if I can improve my approch to compute faster.

Let me share my code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Solution {

    private static List<Integer> listPossibleValues;
    private static int maxStone;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        if (1 <= t && t <= 10) {
            while (t-- > 0)
                getPossibleLastValue(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
        }
    }

    private static void getPossibleLastValue(int n, int a, int b) {
        maxStone = n;
        listPossibleValues = new ArrayList<Integer>();
        int stone = 0;
        getNextStone(stone,0, a, b);
        Collections.sort(listPossibleValues);
        System.out.println(listPossibleValues.toString().replace("[", "").replace("]", "").replace(",", ""));
    }

    private static void getNextStone(int stone, int lastValue, int a, int b) {

        int newLastA = lastValue + a;
        int newLastB = lastValue + b;

        stone++;
        if (stone < maxStone -1){
            getNextStone(stone,newLastA,a,b);
            getNextStone(stone,newLastB,a,b);
        }
        else
        {
            if(!listPossibleValues.contains(newLastA)){
                listPossibleValues.add(newLastA);
            }
            if(!listPossibleValues.contains(newLastB)){
                listPossibleValues.add(newLastB);
            }
        }
    }
}

My testcase sample:

n = 3
a = 1
b = 2
2 3 4

n = 4
a = 10
b = 100
30 120 210 300

n = 9
a = 25
b = 59
200 234 268 302 336 370 404 438 472

n = 18
a = 28
b = 28
476

n = 12
a = 26
b = 35
286 295 304 313 322 331 340 349 358 367 376 385

[~s.o.s~]

There are two main problems with your above approach:

1. Using the wrong datastructure
2. Needless repeated computationss burning the CPU

Contains check on a List data structure is expensive due to its O(n) nature and should be avoided; prefer using a Set variant like HashSet.

The needless computation aspect of this problem is very similar to when you are recursively computing factorials. If you want 5! and you are using the naive approach, you end up computing stuff needlessly an exponential number of times. Try tracing the recursive call 10! on a piece of paper to understand more.

If you log the values passed to the method getNextStone, you'll see it getting called countless times for the same set of inputs. The solution here is to use memoization and remember the result of the computations instead of getting into the recursive death spiral. A small change to your code and it now runs pretty fast IMO.

// Java 8 specific code; you might have to change it
class Solution {

    private static HashSet<Integer> listPossibleValues;

    private static HashSet<String> alreadyComputed = new HashSet<>();

    private static int maxStone;

    private static int cnt = 0;

    public static void main(int n, int a, int b) {
        long start = System.nanoTime();
        getPossibleLastValue(n, a, b);
        System.out.printf("It took %s milliseconds for naive approach%n%n", TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - start));
    }

    private static void getPossibleLastValue(int n, int a, int b) {
        maxStone = n;
        listPossibleValues = new HashSet<Integer>();
        int stone = 0;
        getNextStone(stone, 0, a, b);
        System.out.println(listPossibleValues.stream().sorted().collect(Collectors.toList()));
        System.out.printf("Count=%s%n", cnt);
    }

    private static void getNextStone(int stone, int lastValue, int a, int b) {
        String key = stone + "|" + lastValue;
        if (alreadyComputed.contains(key)) {
            return;
        }

        cnt++;
        int newLastA = lastValue + a;
        int newLastB = lastValue + b;

        stone++;
        if (stone < maxStone - 1) {
            getNextStone(stone, newLastA, a, b);
            getNextStone(stone, newLastB, a, b);
        } else {
            if (!listPossibleValues.contains(newLastA)) {
                listPossibleValues.add(newLastA);
            }
            if (!listPossibleValues.contains(newLastB)) {
                listPossibleValues.add(newLastB);
            }
        }
        alreadyComputed.add(key);
    }
}

[thegreymatter]

Hi ~S.o.S~

Thanks for your reply.

Pointless traversing was really so silly of me. Should have been bit careful on that.

Performance comparison of List vs Set did matter when my input got even bigger. Shouldn't have been obsessed with List.

[JeffGrigg]

There is something to be said for stepping back from the code and problem, and giving a really good "think" to the problem and how one could solve it.

I found that I can solve it in order n time. Properly simplified, it can be done by hand. (Of course, n = 1000, a = 1, b = 2 would be kind of tedius. ;-)

Notice that there are always n results. (...except when a == b -- when there is only one result -- a * (n - 1).) And the results have a predictable pattern.

It might help to consider what results to expect for n = 1, 2, 3, ... in sequence, and look for patterns:

n = 1
0 + <nothing> = 0

n = 2
0 + a = a
0 + b = b
two results: a, b

n = 3
0 + a + a = 2a
0 + a + b = a + b
0 + b + a = a + b
0 + b + b = 2b
Three results. Notice that order doesn't really matter. a + b is the same thing as b + a. Maybe we can use that, to find a more efficient approach. ;->

n = 4
0 + a + a + a = 3a

0 + a + a + b = 2a + b
0 + a + b + a = 2a + b
0 + b + a + a = 2a + b

0 + a + b + b = a + 2b
0 + b + a + b = a + 2b
0 + b + b + a = a + 2b

0 + b + b + b = 3b

Notice the two groups of duplicates. There must be some way we can "count through" the n results, hitting just one example of each of the sets of duplicates, and be sure to hit all unique sums.

And there is a way. Probably several similar ways. I'll let you think about it.

;->

[JeffGrigg]

I made some GUnit tests for it:

import junit.framework.TestCase;
import java.util.TreeSet;

public class SolutionTest extends TestCase {

    public void testN0() {
        assertEquals(new TreeSet<Integer>() {}, Solution.getPossibleLastValue(0, 1, 2));
    }

    public void testN1() {
        assertEquals(toSet(new int[] {0}), Solution.getPossibleLastValue(1, 1, 2));
    }

    public void testN2() {
        assertEquals(toSet(new int[] {1, 2}), Solution.getPossibleLastValue(2, 1, 2));
    }

    public void testN2_OtherValues() {
        assertEquals(toSet(new int[] {3, 5}), Solution.getPossibleLastValue(2, 3, 5));
    }

    public void testN2_Reverse() {
        assertEquals(toSet(new int[] {3, 5}), Solution.getPossibleLastValue(2, 5, 3));
    }

    public void testN3() {
        assertEquals(toSet(new int[] {4, 7, 10}), Solution.getPossibleLastValue(3, 2, 5));
    }

    public void testCase1() {
        assertEquals(toSet(new int[] {2, 3, 4}), Solution.getPossibleLastValue(3, 1, 2));
    }

    public void testCase2() {
        assertEquals(toSet(new int[] {30, 120, 210, 300}), Solution.getPossibleLastValue(4, 10, 100));
    }

    public void testCaseSamplesA() {
        assertEquals(toSet(new int[] {2, 3, 4}), Solution.getPossibleLastValue(3, 1, 2));
    }

    public void testCaseSamplesB() {
        assertEquals(toSet(new int[] {30, 120, 210, 300}), Solution.getPossibleLastValue(4, 10, 100));
    }

    public void testCaseSamplesC() {
        assertEquals(toSet(new int[] {200, 234, 268, 302, 336, 370, 404, 438, 472}), Solution.getPossibleLastValue(9, 25, 59));
    }

    public void testCaseSamplesD() {
        assertEquals(toSet(new int[] {476}), Solution.getPossibleLastValue(18, 28, 28));
    }

    public void testCaseSamplesE() {
        assertEquals(toSet(new int[] {286, 295, 304, 313, 322, 331, 340, 349, 358, 367, 376, 385}), Solution.getPossibleLastValue(12, 26, 35));
    }

    private static TreeSet<Integer> toSet(final int[] values) {
        final TreeSet<Integer> result = new TreeSet<>();
        for (final int value : values) {
            result.add(value);
        }
        return result;
    }

}

[JeffGrigg]

This is my solution:

    public static TreeSet<Integer> getPossibleLastValue(final int n, int a, int b) {
        final TreeSet<Integer> result = new TreeSet<>();
        if (n == 1) {
            result.add(0);
        } else if (n > 1) {
            int value = a * (n - 1);
            for (int idx = 0; idx < n; ++idx) {
                result.add(value);
                value += b - a;
            }
        }
        return result;
    }