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

[royaldeveloper-rajgiri]

class Solution {
private String s;
private Long[][][][][] memoCnt;
private Long[][][][][] memoSum;

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

private long calc(long n) {
    if (n < 0) return 0;
    s = Long.toString(n);
    int m = s.length();
    memoCnt = new Long[m][11][11][2][2];
    memoSum = new Long[m][11][11][2][2];
    return dfs(0, 10, 10, 0, 1)[1];
}

private long[] dfs(int pos, int pp, int pr, int st, int tight) {
    if (pos == s.length()) {
        return new long[]{1L, 0L};
    }
    if (memoCnt[pos][pp][pr][st][tight] != null) {
        return new long[]{
            memoCnt[pos][pp][pr][st][tight],
            memoSum[pos][pp][pr][st][tight]
        };
    }

    int limit = (tight == 1) ? s.charAt(pos) - '0' : 9;
    long totalCnt = 0;
    long totalSum = 0;

    for (int d = 0; d <= limit; d++) {
        int ntight = (tight == 1 && d == limit) ? 1 : 0;

        if (st == 0 && d == 0) {
            long[] res = dfs(pos + 1, 10, 10, 0, ntight);
            totalCnt += res[0];
            totalSum += res[1];
        } else {
            long added = 0;
            if (st == 1 && pp != 10) {
                if ((pr > pp && pr > d) || (pr < pp && pr < d)) {
                    added = 1;
                }
            }

            int npp = (st == 1) ? pr : 10;
            long[] res = dfs(pos + 1, npp, d, 1, ntight);
            totalCnt += res[0];
            totalSum += res[1] + added * res[0];
        }
    }

    memoCnt[pos][pp][pr][st][tight] = totalCnt;
    memoSum[pos][pp][pr][st][tight] = totalSum;
    return new long[]{totalCnt, totalSum};
}

}