372. Super Pow

MediumMathDivide and Conquer
Leetcode Link

Problem Description

The problem requires us to calculate a^b mod 1337, where a is a positive integer and b is an extremely large positive integer presented as an array. The notation a^b refers to a raised to the power b. The array represents the number b where each element is a digit of b in its base-10 (decimal) representation. The least significant digit is at the end of the array.

Intuition

To deal with the extremely large exponent b efficiently, we need to apply modular exponentiation. Calculating a^b directly, even before applying the modulus, is not feasible because b can be very large. Instead, we can repeatedly use the property (x * y) mod z = [(x mod z) * (y mod z)] mod z to keep the intermediary results small.

Also, we can apply the right-to-left binary method for exponentiation, which goes through each digit of the exponent, in our case each element in array b. For each digit d in b from right to left, we compute (a^d) mod 1337 and multiply it with the running ans. After processing a digit d, we must update a to a^10 mod 1337 to account for the positional value of d in b. This is because each step to the left in the array represents a decimal place increase by a factor of 10, effectively multiplying our base a by 10^d.

By starting from the least significant digit of b (the end of the array) and working our way back to the most significant digit, each iteration computes the result for one decimal place, while updating a to its new base raised to the power of 10.

The reason we perform operations under modulo 1337 at every step is to prevent overflow and ensure that all intermediate multiplication results are manageable for large inputs.

Learn more about Math and Divide and Conquer patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search can be used to find whether two components in a graph are connected.

Solution Approach

The solution uses a basic loop and modular arithmetic to solve the problem of computing (a^b) mod 1337. Let's go through the steps:

  1. Initialize ans to 1 because anything raised to the power 0 is 1, and it will be our cumulative product for the result.
  2. Iterate over the digits of b in reverse order, i.e., from the least significant digit to the most significant digit.
  3. In each iteration of the loop, we update ans using the formula ans = ans * (a^e) mod 1337. Here e is the current digit of b. The expression (a^e) mod 1337 computes the contribution of the current digit to the overall exponentiation.
  4. After processing each digit e, we need to update a to account for shifts in decimal place. We use the formula a = (a^10) mod 1337.
  5. After the loop ends, ans holds the final value of (a^b) mod 1337.

In this approach, pow(x, y, z) is a powerful built-in Python function that calculates (x^y) mod z efficiently (modular exponentiation), even for large values of y.

By iteratively handling each digit of b and applying modular arithmetic at every step, we maintain manageable numbers throughout the computation process. This is necessary because working with significantly large numbers directly would be impractical due to computational and memory constraints.

The pattern used here is that of repeated squaring, which is a standard technique in modular exponentiation algorithms where the base is squared (or here raised to the power of 10) for each successive digit. This is premised on the mathematical insight that squaring the base adjusts for the exponential increase as you move through each digit of the exponent.

This also preserves the order of computation represented by the array b, properly accounting for each digit's positional value, ending with a correct answer modulo 1337.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Example Walkthrough

Let's illustrate the solution approach with a small example.

Assume a = 2, and b is represented by the array [1, 0, 2], which corresponds to the integer 201.

The goal is to compute (2^201) mod 1337.

Following the solution steps:

  1. Initialize ans to 1. Initially, ans = 1.

  2. The array [1, 0, 2] represents the number 201. We iterate over it from the end (right-to-left):

    • Starting with the least significant digit, which is 2 in this case, we compute (2^2) mod 1337. This is 4.
    • Update ans with this value by multiplying: ans = 1 * 4 mod 1337, which simplifies to ans = 4.

  3. Now, before moving to the next digit, we must update a to a^10 mod 1337 to account for the positional value:

    • Update a with (2^10) mod 1337, which is equal to 1024 mod 1337. This is 1024.
    • The new value of a is now 1024.

  4. Moving to the second digit from the end, which is 0:

    • Compute (1024^0) mod 1337, which is 1.
    • Update ans = 4 * 1 mod 1337, so ans remains 4.

  5. Again, we must update a to the next power of ten:

    • Update a with (1024^10) mod 1337. Here we use the power function pow(1024, 10, 1337). Let's assume this calculation gives us the value X for simplicity.
    • Now a becomes X.

  6. Finally, moving to the most significant digit, which is 1:

    • Compute (X^1) mod 1337, which just yields X.
    • Update ans = 4 * X mod 1337.

  7. After processing all digits, the value stored in ans is (2^201) mod 1337.

This example walked through each iteration, updating ans with the contribution of each digit in the array b, and recalculating the base a as a^10 mod 1337 after each step.

Keep in mind that for the actual computing of the updated value of a as a^10 mod 1337, especially for large values of a, the pow function is used due to its efficient computation of large exponents under a modulus.

Solution Implementation

1class Solution:
2    def superPow(self, base: int, exponent_digits: List[int]) -> int:
3        # Define the modulus to ensure the result is within a reasonable range
4        mod = 1337
5      
6        # Initialize the answer to 1, as we'll be multiplying it iteratively
7        result = 1
8      
9        # Reverse the list of digits to process the exponent starting from the least significant digit
10        for digit in reversed(exponent_digits):
11            # Multiply the current result by base to the power of the current digit, 
12            # then take the modulus to keep it within the defined range.
13            result = (result * pow(base, digit, mod)) % mod
14          
15            # Update the base to be raised to the next power of 10, again within the modulus range.
16            # This accounts for shifting one decimal place to the left in the exponent.
17            base = pow(base, 10, mod)
18      
19        # Return the final result after processing all digits in the exponent
20        return result
21
1class Solution {
2    private final int MOD = 1337; // Using all-uppercase for the constant value to follow Java naming conventions
3
4    /**
5     * Calculates a^b mod 1337 where a is an integer and b is represented as an array of digits.
6     *
7     * @param a The base number.
8     * @param b The exponent represented as an array of digits.
9     * @return The result of a^b mod 1337.
10     */
11    public int superPow(int a, int[] b) {
12        long result = 1; // Initialize result to 1.
13
14        // Loop through the array from the last element to the first element.
15        for (int i = b.length - 1; i >= 0; --i) {
16            // Multiply the result with the fast power of a raised to the current digit, then take mod.
17            result = result * fastPower(a, b[i]) % MOD;
18            // Update a to a^10 to get the next power level for the next digit.
19            a = fastPower(a, 10);
20        }
21        return (int) result; // Cast result back to int before returning.
22    }
23
24    /**
25     * Fast power algorithm calculates a^n mod 1337.
26     *
27     * @param a The base number.
28     * @param n The exponent.
29     * @return The result of a^n mod 1337.
30     */
31    private long fastPower(long a, int n) {
32        long ans = 1; // Result of the exponentiation.
33
34        // Loop through the bits of n until n is 0.
35        for (; n > 0; n >>= 1) {
36            // Whenever the current bit is 1, multiply ans with a and take mod.
37            if ((n & 1) == 1) {
38                ans = ans * a % MOD;
39            }
40            // Square a and take mod for the next iteration (or next bit).
41            a = a * a % MOD;
42        }
43        return ans; // Return the power result.
44    }
45}
46
1class Solution {
2public:
3    int superPow(int base, vector<int>& digits) {
4        // Define the modulus constant as required by the problem statement.
5        const int MOD = 1337;
6      
7        // Result of the super power operation, initialized to 1.
8        long long result = 1;
9
10        // Define a lambda function for fast exponentiation under modulus.
11        // It calculates (base^exponent) % MOD using the binary exponentiation method.
12        auto quickPow = [&](long long base, int exponent) -> int {
13            long long res = 1; // Initialize the result of exponentiation to 1.
14            while (exponent > 0) {
15                if (exponent & 1) {
16                    // If the current exponent bit is set, multiply the result by base.
17                    res = (res * base) % MOD;
18                }
19                // Square the base and reduce it modulo MOD for the next bit of exponent.
20                base = (base * base) % MOD;
21                // Right-shift exponent by one bit to process the next bit.
22                exponent >>= 1;
23            }
24            // Cast the long long result to int before returning.
25            return static_cast<int>(res);
26        };
27
28        // Process the array of digits in reverse order to calculate the super power.
29        for (int i = digits.size() - 1; i >= 0; --i) {
30            // Multiply the result by (base^(current digit)) % MOD.
31            result = (result * quickPow(base, digits[i])) % MOD;
32            // Update base to base^10 for the next iteration (digit place).
33            base = quickPow(base, 10);
34        }
35
36        // Return the final result as an integer.
37        return static_cast<int>(result);
38    }
39};
40
1function superPow(base: number, digits: number[]): number {
2    let result = 1; // Initialize result variable
3    const modulo = 1337; // Define the modulo value for calculations to avoid large numbers
4
5    // Helper function for quick exponentiation under modulus
6    const quickPow = (base: number, exponent: number): number => {
7        let localResult = 1; // Initialize local result for this function
8        while (exponent > 0) { // Loop until exponent is zero
9            if (exponent & 1) { // If the current bit is set
10                localResult = Number((BigInt(localResult) * BigInt(base)) % BigInt(modulo));
11            }
12            base = Number((BigInt(base) * BigInt(base)) % BigInt(modulo)); // Square the base
13            exponent >>= 1; // Right shift exponent by 1 (divide by 2 and take floor)
14        }
15        return localResult; // Return the calculated power
16    };
17
18    // Start from the least significant digit of the array
19    for (let i = digits.length - 1; i >= 0; --i) {
20        result = Number((BigInt(result) * BigInt(quickPow(base, digits[i]))) % BigInt(modulo));
21        base = quickPow(base, 10); // Elevate the base to the 10th power for the next iteration
22    }
23
24    return result; // Return final result
25}
26
Not Sure What to Study? Take the 2-min Quiz：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is determined by the for-loop which iterates through the list b. Since the length of b dictates the number of iterations, let's call the length of b be n.

During each iteration, there are two main operations.

  1. ans = ans * pow(a, e, mod) % mod: Computational complexity for pow(a, e, mod) function is generally O(log(e)) for each iteration. However, since e is a single digit (0-9) as per the problem statement of superPow on LeetCode, the time complexity for pow(a, e, mod) becomes O(1) for each iteration.

  2. a = pow(a, 10, mod): Here the base a is raised to the power of 10. Similar to the previous point, this would normally be O(log(10)), but since 10 is a constant, this operation is also O(1).

The loop runs n times, and each iteration performs a constant number of O(1) operations. Therefore, the overall time complexity is O(n).

Space Complexity

The space complexity of the solution is determined by the extra space used in addition to the input.

  1. The variable ans and other temporary variables use a constant amount of space, contributing to an O(1) space complexity.
  2. The input list b is not duplicated, and reversing the list using b[::-1] does not create a new list, it creates an iterator, which is more space-efficient.
  3. There are no recursive calls or additional data structures that would use extra space.

Therefore, the space complexity of the algorithm is O(1), as it uses a constant amount of extra space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫