solution in java for question number 3753

[tarangharsola]

class Solution {
    private String s;
    private long[][] memo;

    public long totalWaviness(long num1, long num2) {
        return countUpTo(num2) - countUpTo(num1 - 1);
    }

    private long countUpTo(long n) {
        if (n <= 0) return 0;
        s = Long.toString(n);
        memo = new long[16 * 2 * 11 * 11 * 2][2];
        for (long[] row : memo) row[0] = -1;
        return dp(0, 1, 10, 10, 0)[0];
    }

    private long[] dp(int pos, int tight, int dPrev, int dPrev2, int started) {
        int L = s.length();
        if (pos == L) return new long[]{0, started};

        int key = ((((pos * 2 + tight) * 11 + dPrev) * 11 + dPrev2) * 2 + started);
        if (memo[key][0] != -1) return memo[key];

        int limit = tight == 1 ? (s.charAt(pos) - '0') : 9;
        long tw = 0, tc = 0;

        for (int d = 0; d <= limit; d++) {
            int nt = (tight == 1 && d == limit) ? 1 : 0;
            if (started == 0 && d == 0) {
                long[] res = dp(pos + 1, nt, 10, 10, 0);
                tw += res[0]; tc += res[1];
            } else {
                int added = 0;
                if (started == 1 && dPrev2 != 10) {
                    if (dPrev > dPrev2 && dPrev > d) added = 1;
                    else if (dPrev < dPrev2 && dPrev < d) added = 1;
                }
                int nd2 = (started == 1) ? dPrev : 10;
                long[] res = dp(pos + 1, nt, d, nd2, 1);
                tw += res[0] + (long) added * res[1];
                tc += res[1];
            }
        }

        memo[key][0] = tw;
        memo[key][1] = tc;
        return memo[key];
    }
}

• for verification you can check here

[StarsExpress]

Just make a pull request for that question, and your solution code gets reviewed for potential merge into main if all things are ok.

Contribution Guidelines