Solution by gunpreetahuja


  • 0
    G

    Approach #1 Brute Force [Time Limit Exceeded]

    Intuition

    Convert the array(or list) b to an integer using for loop.

    Algorithm

    Python

    class Solution(object):
        def superPow(self, a, b):
            """
            :type a: int
            :type b: List[int]
            :rtype: int
            """
            num = 0
            count = len(b) -1
            for i in b:
                num += i*10**count
                count -= 1
            power = a ** num % 1337
            return power
    

    Complexity Analysis

    • Time complexity : $$O(len(b))$$.
      We need a for loop that runs as per the length of array b. Rest of the operations(count, power computation, etc.) are of constant time.

    • Space complexity : $$O(1)$$. We need 1 space for count, 1 space for num and 1 for power, which gives constant space complexity.


    Approach #2 Built-In Functions Usage [Accepted]

    Intuition

    Use the map() function to convert the integer list to list of strings, followed by the join() function to concatenate the list into a single string which is, then, type-casted to an integer.
    The built-in 3-parameter pow() function is used to calculate the power and modulo together using a single step.

    Algorithm

    Python

    class Solution(object):
        def superPow(self, a, b):
            """
            :type a: int
            :type b: List[int]
            :rtype: int
            """
            num = 0
            count = len(b) -1
            num = "".join(map(str, b))
            power = pow(a, int(num), 1337)
            return power
    

    Complexity Analysis

    • Time complexity : $$O(1)$$, consider each built-in function taking a constant time.

    • Space complexity : $$O(1)$$. Same as the previous approach. We need $$O(1)$$ space to store num, power and count.


Log in to reply
 

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