Why do I pass the custom testcases but get a runtime error when submitting?


  • 0
    A

    I have passed the custom testcases. But when I submitted my c++ solution, I got a runtime error with last executed input: 3. I didn't use any global or static variables. Could somebody help me?

    Here's my code.

    class Solution {
    public:    
        int countPrimes(int n) {
            vector<int> primes;
            vector<vector<int>> phi;
            vector<int> pi;
            
            primes.clear();
            phi.clear();
            pi.clear();
        
            init(primes, phi, pi, min(n, 2000000));
            return lehmer(primes, phi, pi, n - 1); // less than or equal to n-1
        }
        
    private:
        void init(vector<int>& primes, vector<vector<int>>& phi, vector<int>& pi, int N) {
            phi.reserve(100);
            pi.push_back(0);
            
            vector<int> a((N >> 6) + 2, 0);
            setBit(a, 0);
            setBit(a, 1);
            for (int i = 3; i * i < N; i += 2)
                if (!getBit(a, i))
                    for (int j = i * i; j < N; j += i << 1) setBit(a, j);
            for (int i = 1; i < N; ++i) {
                pi.push_back(pi.back());
                if ((2 == i) || (i && (i & 1) && !getBit(a, i))) {
                    primes.push_back(i);
                    ++pi[i];
                }
            }
            for (int i = 0; i < 100; ++i) {
                int sz = min((int)primes.size(), 10000);
                phi[i].reserve(sz);
                for (int j = 0; j < sz; ++j)
                    if (0 == j) phi[i][j] = i;
                    else phi[i][j] = phi[i][j-1] - phi[i / primes[j-1]][j-1];
            }
        }
        
        void setBit(vector<int>& a, int k) {
            a[k >> 6] |= 1 << ((k >> 1) & 0x1f);
        }
        
        int getBit(vector<int>& a, int k) {
            return a[k >> 6] & (1 << ((k >> 1) & 0x1f));
        }
        
        int getPhi(vector<int>& primes, vector<vector<int>>& phi, vector<int>& pi, int n, int m) {
            if (0 == m) return n;
            if (primes[m-1] >= n) return 1;
            if ((n < 100) && (m < 10000)) return phi[n][m];
            return getPhi(primes, phi, pi, n, m-1) - getPhi(primes, phi, pi, n / primes[m-1], m-1);
        }
        
        int lehmer(vector<int>& primes, vector<vector<int>>& phi, vector<int>& pi, int n) {
            if (n < 0) return 0;
            if (n < 2000000) return pi[n];
            
            int t1 = pi[(int)cbrt((double)n + 0.9)];
            int t2 = (int)sqrt((double)n + 0.9);
            int retval = getPhi(primes, phi, pi, n, t1) + t1 - 1;
            for (int i = t1; primes[i] <= t2; ++i)
                retval = retval - lehmer(primes, phi, pi, n / primes[i]) + lehmer(primes, phi, pi, primes[i]) - 1;
            return retval;
        }
    };
    

Log in to reply
 

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