Project Euler, Problem #529 10-substrings

Question

Have anyone tried the problem 529? I tried but I'm confronted to a very high complexity $O(N^2)$ with $N$ being the length of the number. The code is:

public static boolean is10Friendly(long num) {
    List<Integer> numbers = new ArrayList<>();
    Map<String, Integer> friendly = new HashMap<>();

    int fasterCountTo10 = 0;
    boolean fastValid = false;
    int count = 0;
    while (num > 0) {
        int cur = (int) (num % 10);
        fasterCountTo10 += cur;

        if (fasterCountTo10 == 10)
            fastValid = true;

        numbers.add(cur);
        friendly.put(String.valueOf(cur) + "_" + String.valueOf(count++), 0);

        num /= 10;
    }

    //Cheap check to discard many elements. Gain is speed +30%.
    if (!fastValid) {
        return false;
    }

    for (int i = 0; i < numbers.size(); i++) {
        int counter = 0;
        for (int j = i; j < numbers.size(); j++) {
            counter += numbers.get(j);
            if (counter == 10) {
                for (int jj = i; jj <= j; jj++) {
                    String key = String.valueOf(numbers.get(jj)) + "_" + String.valueOf(jj);
                    Integer val = friendly.get(key);
                    friendly.put(key, ++val);
                }
                break;
            }
            if (counter > 10) {
                break;
            }
        }
    }

    // It must be greater than its frequency
    for (Integer val : friendly.values()) {
        if (val < 1) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {

    long n1 = System.currentTimeMillis();
    for (int p = 2; p <= 10; p++) {
        long count = 0;
        for (long i = 1; i < (long) Math.pow(10, p); i++) {
            if (is10Friendly(i)) {
                count++;
            }
        }
        System.out.println(count + " elapsed time: " + (System.currentTimeMillis() - n1));
        // System.out.println(p + ", count = " + count);
    }

     //System.out.println(is10Friendly(1991)); //false
    // System.out.println(is10Friendly(3523014)); //true
    // System.out.println(is10Friendly(28546)); //false
}

Console Output

9 elapsed time: 3
72 elapsed time: 17
507 elapsed time: 48
3492 elapsed time: 263
23697 elapsed time: 1124

My results seem relevant according to the guidelines. Does anyone know what kind of mathematical model we could use to lower this complexity?

Many thanks in advance!

Answer 1

First 2 notes: (1) a tester for 10friendly won't help you with the problem even if it's O(N) or better cause you can't test 10^(10^18) numbers (2) won't discuss solutions

An O(N) algorism would be:
use 3 positon markers into your numbers list: lo, hi, gap
Initial: lo and hi mark the leftmost block of numbers that sum up to 10, gap points to the right neighbour of hi. Now you move from left to right:

• increment lo (and subtract number from sum) until the sum is below 10,
• then increment hi (augmenting sum) until the sum is 10 or above
• if the sum matches 10: look if gap is covered (lo <= gap) else->fail
• proceed until you pass the right end: now check gap (point inside numbers?)

I prefer thinking of it as tiling problem: if you forget about the zeroes for the moment, there are some 511 tiles (sequences of digits 1-9 with sum 10) and you have to cover your number (or maybe a large space) with these tiles, that may perhaps overlap.

Another note: Both the people from ProjectEuler and Stackexchange prefer that such topics be discused in den PE Forum, see Project Euler $420$