20-line C++ DP O(n)-Time O(1)-Space Solution


  • 0

    EDIT::: After I "overloaded" the operator +(by a method, because operators of primitive type cannot be overloaded) to include the mod, and using ints rather than unordered_map, it passed. AxLy means a record with x As, y ending Ls.

    class Solution {
    public:
        int& add(int& a, int b) {
            return a = (a+b)%1000000007;
        }
        
        int checkRecord(int n) {
            int A0L0 = 1, A0L1 = 1, A0L2 = 0, A1L0 = 1, A1L1 = 0, A1L2 = 0;
            while(--n) {
                int newA0L0 = 0, newA0L1 = 0, newA0L2 = 0, newA1L0 = 0, newA1L1 = 0, newA1L2 = 0;
                // appending a P
                add(add(add(newA0L0, A0L0), A0L1), A0L2); //newA0L0 = A0L0 + A0L1 + A0L2;
                add(add(add(newA1L0, A1L0), A1L1), A1L2); //newA1L0 = A1L0 + A1L1 + A1L2;
                // appending an A
                add(add(add(newA1L0, A0L0), A0L1), A0L2); //newA1L0 = newA1L0 + A0L0 + A0L1 + A0L2;
                // appending an L
                add(newA0L1, A0L0); //newA0L1 = A0L0;
                add(newA0L2, A0L1); //newA0L2 = A0L1;
                add(newA1L1, A1L0); //newA1L1 = A1L0;
                add(newA1L2, A1L1); //newA1L2 = A1L1;
                A0L0 = newA0L0; A0L1 = newA0L1; A0L2 = newA0L2; A1L0 = newA1L0; A1L1 = newA1L1; A1L2 = newA1L2;
            }
            return add(add(add(add(add(A0L0, A0L1),A0L2),A1L0),A1L1),A1L2);
        }
    };
    

    BEFORE EDIT::: I can get the correct answer up to 28, so I believe the logic is correct. However, I cannot figure out where shall I mod to pass bigger input. Each A values 100, each ending L values 1, so record[100] means how many records with one A and no ending L.

    class Solution {
    public:
        int MOD = 1000000007;
        int checkRecord(int n) {
            unordered_map<int, int> record;
            record[0] = 1;
            record[1] = 1;
            record[100] = 1;
            while(--n) {
                unordered_map<int, int> newRecord;
                // appending a P
                newRecord[0] = record[0]+record[1]+record[2];
                newRecord[100] = record[100]+record[101]+record[102];
                
                // appending an A
                newRecord[100] += record[0]+record[1]+record[2];
                
                // appending an L
                newRecord[1] = record[0];
                newRecord[2] = record[1];
                newRecord[101] = record[100];
                newRecord[102] = record[101];
                
                record = newRecord;
            }
            return record[0]+record[1]+record[2]+record[100]+record[101]+record[102];
        }
    };
    

  • 1
    W

    Basically, mod before you add because the result might overflow.


  • -1
    N

    @luming89 use long (8 bytes) instead of int (4 bytes) to store large number, thus you don't need to worry about overflow.


  • 0

    @niwota The problem requires you to perform mod as the input may reach 100000, which is far beyond the range of long


  • 0
    N

    @luming89
    Every addition just use mod 1000000007 before you store it.

    add(add(add(newA0L0, A0L0), A0L1), A0L2);
    could be rewritten to newA0L0 = (A0L0+A0L1+A0L2) % 1000000007 , where all variables are long type.
    Thus it only requires 1 mod operation instead of calling int& add(int& a, int b) 3 times.


Log in to reply
 

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