1-liners & other with explanations


  • 14

    Solution 1: Using Python's big integers (accepted in 72 ms)

    Turn b into a Python integer object (they grow arbitrarily large) and just use the pow function (which supports a modulo paramenter).

    def superPow(self, a, b):
        return pow(a, int(''.join(map(str, b))), 1337)
    

    ## Solution 2: Using small ints (accepted in 80 ms)

    Originally I went backwards (see solution 5) but then I saw other people go forwards and it's simpler. Sigh. Anyway... my version:

    def superPow(self, a, b):
        result = 1
        for digit in b:
            result = pow(result, 10, 1337) * pow(a, digit, 1337) % 1337
        return result
    

    Explanation: For example for a5347, the above computes a5, then a53, then a534, and then finally a5347. And a step from one to the next can be done like a5347 = (a534)10 * a7.


    ## Solution 3: Using recursion (accepted in 92 ms)

    Obligatory recursive oneliner version of solution 2.

    def superPow(self, a, b):
        return pow(a, b.pop(), 1337) * pow(self.superPow(a, b), 10, 1337) % 1337 if b else 1
    

    ## Solution 4: Using `reduce` (accepted in 80 ms)

    Obligatory reduce-oneliner version of solution 2.

    def superPow(self, a, b):
        return reduce(lambda result, digit: pow(result, 10, 1337) * pow(a, digit, 1337) % 1337, b, 1)
    

    ## Solution 5: omg was i stupid (accepted in 72 ms)

    My original do-it-yourself before I saw other people's solutions and wrote solutions 2-4.

    Using only small ints, also accepted in 72 ms:

    def superPow(self, a, b):
        result = 1
        apower = a
        for digit in reversed(b):
            result = result * pow(apower, digit, 1337) % 1337
            apower = pow(apower, 10, 1337)
        return result
    

    Explanation by example:

    a5347
    = a5000 * a300 * a40 * a7
    = (a1000)5 * (a100)3 * (a10)4 * a7
    = (((a10)10)10)5 * ((a10)10)3 * (a10)4 * a7

    Computing that from back to front is straightforward (or straightbackward?).


  • 5
    R

    In Java

    public class Solution {
        public int superPow(int a, int[] b) {
            int res = 1;
            int p = a;
            for(int i = b.length - 1; i >=0; i--){
                res = res * pow(p,b[i],1337)%1337;
                p = pow(p, 10,1337);
            }
            return res;
        }
        public int pow(int a, int b, int c) {
            long res = 1;
            long p = a;
            while (b > 0) {
                if ((b & 1) == 1) { 
                    res = (res * p) % c;
                }
                p = (p * p) % c;
                b >>= 1;
            }
            return (int)(res % c);
        }
    }
    

  • 1
    H

    @StefanPochmann
    Time complexity?
    I think it is O(N) where N is length of input array size.
    Since we always keep result value < 1337, and power number always <= 10.
    What do you think?


  • 1

    @hpplayer Yes, should be O(n) for solutions 2-5. Just not for solution 1, as converting strings to ints looks like only O(n2):

    >>> from timeit import timeit
    >>> for e in range(10, 21):
            s = '7' * 2**e
            print e, timeit(lambda: int(s), number=1)
    
    10 6.28627033657e-05
    11 0.000146893459905
    12 0.000254658094247
    13 0.00129381706825
    14 0.00357226933718
    15 0.0142666263832
    16 0.0555866661792
    17 0.220853354784
    18 0.880748810259
    19 3.5156306829
    20 14.1526550191
    

Log in to reply
 

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