C++ 9x Faster Solution (Non Math)


  • 0
    class Solution {
    private:
    	inline int calPow(int a, int b) {
    		if(b == 0) return 1;
    		long long t = calPow(a, b / 2);
    		return b & 1 ? (t * t * a) % 1337 : (t * t) % 1337;
    	}
    public:
        int superPow(int a, vector<int>& b) {
        	if(b.empty()) return 1;
            int t = 0, pow = 1;
            for(int i = 0; i < 9; i++) {
            	if(b.empty()) break;
            	t = t + b.back() * pow;
            	pow *= 10;
            	b.pop_back();
            }
            return calPow(superPow(a, b), 1000000000) * calPow(a, t) % 1337;
        }
    };
    

    Explain

    The most common solution is compute it digit by digit, like:

    calPow(superPow(a, b), 10) * calPow(a, t) % 1337;
    

    However, there is still a different way to make it faster.

    First, We can recursively compute a^2k = (a^k)^2, so for pow(a, b), then any b < 2^31 can be computed within 32 times '%'. It's a widely used fast pow algorithm.

    Then, for this problem, instead of compute it digit by digit, every time we can compute 9 digits using this algorithm. Make it 9x faster.

    Maybe it's not the fastest algorithm, but it's a common and easy method to make the code faster. As we know, % operation is very time consuming. Using this method, we could significantly reduce the usage of % operation.

    Also, this trick can be used in other problems when we need to compute extremely large integers.


Log in to reply
 

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