Share my 3 different solutions O(n) and O(lg(n)) - Java


  • 0
    T

    The first one is DP. We define dp[n][0] as the number of all valid combination with the last two posts painted in different colors (post[n] != post[n-1]), and, dp[n][1] as the number of all valid combination with the last two posts painted in the same color (and of course, post[n-2] is painted in different color with post[n-1], in other word, post[n] == post[n-1] != post[n-2]). It is obvious that the total number of valid combination is dp[n][0] + dp[n][1].

    How to calculate dp[n] from dp[n-1]? To get dp[n][0], we just need to pick a color for post[n] that is different from post[n-1]. There are totally (k-1) options for a given color of post[n-1]. To get dp[n][1], the only way is to pick a color for post[n] that is the same as post[n-1]. So, dp[n][0] = (k-1) * (dp[n-1][0] + dp[n-1][1]); dp[n][1] = dp[n-1][0].

    The code is pretty straight forward:

     public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        int[][] dp = new int[n + 1][2];
        dp[1][0] = k;
        for (int i = 2; i <= n; i++) {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1);
            dp[i][1] = dp[i - 1][0];
        }
    
        return dp[n][0] + dp[n][1];
    }
    

    As we can see only dp[i-1] is used to calculate dp[i], there is no need to keep dp[i-2], dp[i-3] ...

    So, the code can be simplified:

    public int numWays(int n, int k) {
        if (n == 0) return 0;
    
        int one = k, two = 0;
        for(int i = 1; i < n; i++) {
            one = (two + (two = one)) * (k-1);
        }
    
        return one + two;
    }
    

    The second solution is basically the same as above except using O(0) space.

    The third try is matrix multiplication. If we exam the above DP carefully, we can tell:
    dp[n] = dp[n-1] * {{k-1, 1}, {k-1, 0}} = dp[n-2] * {{k-1, 1}, {k-1, 0}} * {{k-1, 1}, {k-1, 0}} = .... // matrix multiplication

    So, dp[n] = dp[1] * ({{k-1, 1}, {k-1, 0}} ^ (n-1)). Fortunately, we have a way to calculate the power of a matrix in O(lg(n)) runtime where n is the power.

    public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
    
        int[][] next = {{k - 1, 1}, {k - 1, 0}};
        int[][] pow = pow(next, n - 1);
    
        return k * (pow[0][0] + pow[0][1]);
    }
    
    private int[][] pow(int[][] matrix, int n) {
        int[][] ans = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ans = multiplication(ans, matrix);
            }
            matrix = multiplication(matrix, matrix);
            n >>= 1;
        }
        return ans;
    }
    
    private int[][] multiplication(int[][] m1, int[][] m2) {
        int[][] ans = new int[2][2];
        ans[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
        ans[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
        ans[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
        ans[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
        return ans;
    }
    

    In theory, the third solution is O(lg(n)), but since the test case is pretty small, you don't really see the benefits.


Log in to reply
 

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