Project Euler 113 – Non-bouncy numbers

Problem link

This stood out immediately to me as Dynamic Programming, although I’m certain with a bit of ingenuity you could come up with a closed form equation. I’m lazy though, and will just get the computer to do it for me!

Assume we have a number \(d_1 d_2 d_3 \ldots d_n\) where \(\forall_{i} 0 \leq d_i \leq 9\) except the for the first digit we have \(d_1 \neq 0\) as a number can’t start with a zero.

Then, consider how to count the number of increasing numbers of length \(i\) beginning with the digit \(k\)

\[ \begin{align} f_{inc}(1,k) &= 1 \\ f_{inc}(i,k) &= \sum_{j=k}^9 f_{inc}(i-1,j) \end{align} \]

Similarly for decreasing numbers except we have to take care of the zero.

\[ \begin{align} f_{dec}(1,k) &= 1 \\ f_{dec}(1,0) &= 1 \\ f_{dec}(i,k) &= \sum_{j=0}^k f_{dec}(i-1,j) \end{align} \]

Now, given \(N\) we can compute how many non-bouncy numbers of length at most \(N\) there are. We count all the increasing numbers beginning with all possible digits and we count all the decreasing digits beginning with all the possible digits. There is a problem: We have double counted numbers like \(111\), or \(3333\), basically all numbers composed of the same digits. For every length \(N\), there are only exactly \(9\) such numbers so we can just easily subtract that.

Then the answer for the how many non-bouncy numbers of length at most \(N\) there are is:

\[ total(N) = \sum_{i=0}^{100} \sum_{k=1}^{9} \left( f_{inc}\left(i,k\right) + f_{dec}\left(i,k\right) \right) - 9N \]

Now we can convert this to Java code. You could convert it to only use one array but for sake of simplicity I used two arrays.

import java.util.*;

public class Euler113{
    
    long[][] DPi;
    long[][] DPd;
    
    public static void main(String[] args){
        Euler113 e = new Euler113();
        System.out.println(e.run());
    }
    
    long run(){
        this.DPi = new long[110][10];
        for(long[] is : this.DPi) Arrays.fill(is,-1);
        for(int i = 1; i <= 9; i++) DPi[1][i] = 1;
        
        this.DPd = new long[110][10];
        for(long[] is : this.DPd) Arrays.fill(is,-1);
        for(int i = 1; i <= 9; i++) DPd[1][i] = 1;
        for(int i = 1; i < 110; i++) DPd[i][0] = 1;
        
        int totalLength = 100;
        long sumIncreasing = 0;
        long sumDecreasing = 0;
        
        for(int i = 1; i <= totalLength; i++) {
            for(int k = 1; k <= 9; k++) {
                sumIncreasing += f_increasing(i,k);
                sumDecreasing += f_decreasing(i,k);
            }
        }
        
        long both = 9*totalLength;
        long totalSum = sumIncreasing + sumDecreasing - both;
        return totalSum;
    }
    
    long f_increasing(int i, int k) {
        if(DPi[i][k] != -1) return DPi[i][k];
        long res = 0;
        for(int j = k; j <= 9; j++){
            res += f_increasing(i-1,j);
        }
        DPi[i][k] = res;
        return res;
    }
    
    long f_decreasing(int i, int k) {
        if(DPd[i][k] != -1) return DPd[i][k];
        long res = 0;
        for(int j = k; j >= 0; j--){
            res += f_decreasing(i-1,j);
        }
        DPd[i][k] = res;
        return res;
    }
}

Run the following, and you get the answer \(51161058134250\) instantly.