C++ Clean and Short Solution


  • 99
    F

    One knowledge: ab % k = (a%k)(b%k)%k
    Since the power here is an array, we'd better handle it digit by digit.
    One observation:
    a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k
    Looks complicated? Let me put it other way:
    Suppose f(a, b) calculates a^b % k; Then translate above formula to using f :
    f(a,1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k;
    Implementation of this idea:

    class Solution {
        const int base = 1337;
        int powmod(int a, int k) //a^k mod 1337 where 0 <= k <= 10
        {
            a %= base;
            int result = 1;
            for (int i = 0; i < k; ++i)
                result = (result * a) % base;
            return result;
        }
    public:
        int superPow(int a, vector<int>& b) {
            if (b.empty()) return 1;
            int last_digit = b.back();
            b.pop_back();
            return powmod(superPow(a, b), 10) * powmod(a, last_digit) % base;
        }
    };
    

    Note: This approach is definitely not the fastest, but it is something one can quickly understand and write out when asked in an interview.
    And this approach is not using any built-in "pow" functions, I think this is also what the interviewer would expect you to do.
    Hope it helps!


  • 3
    J

    why we should do the a %= base ? I cannot understand that...


  • 2
    F

    @Jiming_Ye
    Think about if a is 2147483647, what would it return?


  • 0
    J

    @fentoyal Thanks for your reply. I know we can use a %= base to keep a smaller than base. But, I don't really understand why this manipulation can keep the right output. Because (result * a) % base can be considered as
    (result % base) * (a % base) % base. So a did one more % operation than result? I cannot understand this....


  • 6
    S

    @Jiming_Ye A series of modulo operations on the same base is equivalent to exactly one modulo operation, i.e. (Number % base % base ... % base) == Number % base, so it does not matter if "'a' did one more % operation than result". The whole point of using a%base here is that "result * a" may overflow, but with "(result % base) * (a % base)", we can guarantee there is no overflowing.


  • 0
    J

    @stellari Got it! Thank you very much~~


  • 12

    Great recursive call which reduce the problem by 1 digit a time. Here is Java version.
    b[0,length) is used

    public class Solution {
        public int superPow(int a, int[] b) {
            return superPow(a, b, b.length, 1337);
        }
        
        private int superPow(int a, int[] b, int length, int k) {
            if (length == 1) {
                return powMod(a, b[0], k);
            }
            
            return powMod(superPow(a, b, length - 1, k), 10, k) * powMod(a, b[length - 1], k) % k;
        }
        
        
        //x^y mod k
        private int powMod(int x, int y, int k) {
            x %= k;
            int pow = 1;
            for (int i = 0; i < y; i++) {
                pow = (pow * x) % k;
            }
            return pow; 
        }
    }

  • 0

    what is time complexity of this solution?


  • 0
    F

    @xuyirui It is straightforward: O(n), where n is the length of b.


  • 0

    is that because T(n) = T(n-1) +powmod(10), so T(n) = powmod(10 ) * n ?


  • 1
    F

    @xuyirui For each digit, powmod is called twice. Powmod is running in constant time because k should never be larger than 10, so it is O(19N) worst case.


  • 0

    @fentoyal great explanation. it confused me first because powmod take myPow(n-1) as input, but I realized myPow(n-1) is only computed once.


  • 0
    X
    This post is deleted!

  • 0
    H

    I think there is a typo here:

    a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * a^7 % k

    should be: a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k


  • 0
    F

    @Heartuo You are right. I edited. Thanks,


  • 0

    Does anyone know why In Swift Memory Limit Exceeded?

    struct base {
        static let base = 1337
    }
    
    func superPow(a: Int, _ b: [Int]) -> Int {
        var b = b
        if b.isEmpty {
            return 1
        }
        let lastDigit = b.last!
        b.popLast()
        return powMod(superPow(a, b), 10) * powMod(a, lastDigit) % base.base
    }
    
    func powMod(x: Int, _ y: Int) -> Int {
        let x = x % base.base
        var res = 1
        for _ in 0..<y {
            res = (res * x) % base.base
        }
        return res
    }
    

  • 0
    S

    Thanks for sharing this recursive solution!!!

    Here's a translate in java if anyone is interested.

    private int base = 1337;
    
    public int superPow(int a, int[] b) {
        
        if(b.length==0)  return 1;
        
        int lastDigit = b[b.length-1];
        int[] copyArr = Arrays.copyOf(b, b.length-1);
        
        return powMod(superPow(a,copyArr), 10) * powMod(a,lastDigit) % base;
    }
    
    private int powMod(int a, int n){
        
        a %= base;
        int res = 1;
        
        for(int i=0; i<n;i ++){
            res = (res*a)%base;
        }
        
        return res;
    }
    


  • 0

    revisited % properties, thx! Up voted.


  • 0

    @xuyirui Thanks for your Java version~


  • 0
    T

    Nice idea! The following is edited from yours.

    const int BASEN = 1337;
        int powmod(int a, int n){
            if(n == 0) return 1%BASEN;
            int halfres = powmod(a, n>>1);
            if(n&1) return a* halfres %BASEN * halfres % BASEN;
            else return halfres* halfres % BASEN;
        }
    public: 
        int superPow(int a, vector<int>& b) {
            if(b.empty()) return 1;
            a = a % BASEN;
            int tailb = b.back();
            b.pop_back();
            return powmod(superPow(a, b), 10) * powmod(a, tailb) % BASEN;
        }

Log in to reply
 

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