Idea to make calculation efficient.


  • 2
    C

    I'm not posting my entire solution, since it is correct but ugly, and I definitely need to refactor it. :)

    But the idea is as follows:

    When low.length() == high.length() just use the solution from strobogrammatic-2 and filter out those numbers that are outside range.

    The general case I can explain with an example. Consider low.length() = 4 and high.length() = 10 (just as example).

    For length 4 and length 10, just do as before and use the strobogrammatic-2 solution and filter out candidates that are invalid.

    For all other lengths (here 5, 6, 7, 8, 9), all strobogrammatic numbers of that length are valid, so we can just use a function to count those. Here is that function:

    //how many strobos that are x-digit numbers
    int numStrobos(int xdigitnum) {
        if (xdigitnum <= 0) return 0;
        if (xdigitnum == 1) return 3; //0, 1, 8
        int initialDigs = xdigitnum/2;
        int initCandidates = pow(5, initialDigs-1) * 4;  //0, 1, 6, 8, 9 as digits other than first, 1, 6, 8, 9 as first digits
        int oddCandidates = initCandidates * 3; //0, 1, 8 as middle digits
        return ((xdigitnum % 2) ? oddCandidates : initCandidates);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.