C++ AC recursive solution


  • 3
    S

    The key observation is pow(a,b)%1337 = pow(1337*k+a,b) % 1337

    class Solution {
    public:
     long long myPow(long long num, int k) {
       if (k == 0) return 1;
       if (k == 1) return (num % 1337);
       long long ret = myPow(num % 1337, k / 2) % 1337;
       return (ret * ret * ((k%2) ? num : 1))%1337;
     }
    
     int superPow(int a, vector<int>& b) {
       int L = b.size();
       long long ret = 1;
       for (int i = 0; i < L; i++) {
         ret = (long long)(myPow(ret, 10) * (long long)myPow(a, b[i])) % 1337;
       }
       return ret;
     }
    };
    ```'

  • 0
    D

    Similar to yours. :-)

    class Solution {
    private:
        int powMod(int x, int y) {
            int result{1};
            while (y > 0) {
                if (y & 1) result = (result * x) % 1337;
                y >>= 1;
                x = (x * x) % 1337;
            }
            return result;
        }
    public:
        int superPow(int a, vector<int>& b) {
            a %= 1337;
            int result = 1;
            for (int i = 0; i < b.size(); i++) {
                result = (powMod(result, 10) * powMod(a, b[i])) % 1337;
            }
            return result;
        }
    };
    

  • 0

    @serendip Your myPow is a weird mix of inefficient and complicated... you'd better either store myPow(num % 1337, k / 2) in a variable and use it twice, or recurse only once, to k-1.


  • 0
    S

    @StefanPochmann good points. Updated my solution


  • 0
    H

    @serendip A slight modification where avoid using long long.

    class Solution {
    public:
        int superPow(int a, vector<int>& b) {
            int res = 1;
            for (int i = 0; i < b.size(); ++i) {
                res = myPow(res, 10) * myPow(a, b[i]) % 1337;
            }
            return res;
        }
    private:
        int myPow(int x, int n) {
            if (n == 0) return 1;
            x %= 1337;
            int half = myPow(x, n/2);
            if (n % 2 == 0) return half * half % 1337;
            else return ((half * half) % 1337) * x % 1337;
        }
    };
    

    Similarly, we can use iterative version of myPow. I think the key is that three multiplication is easy to overflow, that's why long long type is required if we did not % 1337 immediately.

    class Solution {
    public:
        int superPow(int a, vector<int>& b) {
            int res = 1;
            for (int i = 0; i < b.size(); ++i) {
                res = myPow(res, 10) * myPow(a, b[i]) % 1337;
            }
            return res;
        }
    private:
        int myPow(int x, int n) {
            int res = 1;
            x %= 1337;
            while (n > 0) {
                if (n & 1) res = res * x % 1337;
                n >>= 1;
                x = x * x % 1337;
            }
            return res;
        }
    };
    

Log in to reply
 

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