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

• 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
// appending an A
// appending an L
A0L0 = newA0L0; A0L1 = newA0L1; A0L2 = newA0L2; A1L0 = newA1L0; A1L1 = newA1L1; A1L2 = newA1L2;
}
}
};
``````

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];
}
};
``````

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

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

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

• @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.

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