Please help with weird behavior of Modulo.


  • 0
    H

    Please help with weird behavior of Modulo.

    I have DP solution as follow, for last statement in the loop I use

    T[r][c] = (T[r][c] + MOD) % MOD;
    

    all test can pass

    but if I use

    T[r][c] = T[r][c] % MOD;
    
    

    There are weired negative result showing up. I can't understand why this happens, why do I have to add MOD(10^9 + 7) before doing modulo operation? the long integer should have no overflow.

    public class Solution {
        
        //equation: T[n,k] = Sum(i= k-n+1 ~ k){T[n-1, i]}
        //T[n,k-1] = Sum(i=0~n-1){T[n-1,k-1-i]}
        
        //recursion: T[n,k] = T[n,k-1] - d(k-n >=0)*T[n-1, k-n] + T[n-1, k]
        //base case: T[*, 0]=1; T[0,*]=0; T[1,*]=0;
        //0<=k<=n*(n-1)
        
        static final long MOD = 1000000007L;
        public int kInversePairs(int n, int k) {
            
            long[][] T = new long[n+1][k+1];
            
            for(int t=0; t<=n; t++){
                T[t][0] = 1;
            }
            
            for(int r=2; r<=n; r++){
                for(int c=1; c<=k ; c++){
                    T[r][c] =   T[r-1][c]
                                - ((c >=r) ? T[r-1][c-r] : 0)
                                + T[r][c-1];
                        
                    T[r][c] = (T[r][c] + MOD) % MOD;
                }
            }
            
            return (int) T[n][k];
        }
    }
    
    

Log in to reply
 

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