372. Super Pow

At a Glance

Topic: math-geometry
Pattern: Modular exponentiation (Divide & Conquer)
Difficulty: Medium
Companies: Amazon, Google, Facebook, ByteDance, Airbnb
Frequency: Low
LeetCode: 372

Problem (one-liner)

Compute base ** exponent mod 1337 where exponent is given as an array of decimal digits (most significant first), representing a large positive integer.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Huge exponent — cannot materialize as integer
"Super pow" / digit array exponent
Fixed modulus 1337

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — impossible exponent range.
Optimal — recursive relation: pow(a, [b0..bk]) = pow(a, [b0..b_{k-1}])**10 * pow(a, bk) (mod m) — O(len * log base) modular multiplies.

Optimal Solution

Go

package main

const modulus = 1337

func superPow(base int, exponent []int) int {
	if len(exponent) == 0 {
		return 1
	}
	lastDigit := exponent[len(exponent)-1]
	prefix := exponent[:len(exponent)-1]
	part := superPow(base, prefix)
	part = modPow(part, 10, modulus)
	part = part * modPow(base, lastDigit, modulus) % modulus
	return part
}

func modPow(base int, exponent int, mod int) int {
	result := 1
	base = base % mod
	for exponent > 0 {
		if exponent%2 == 1 {
			result = result * base % mod
		}
		base = base * base % mod
		exponent /= 2
	}
	return result
}

JavaScript

const MODULUS = 1337;

function superPow(base, exponent) {
	if (exponent.length === 0) {
		return 1;
	}
	const lastDigit = exponent[exponent.length - 1];
	const prefix = exponent.slice(0, -1);
	let part = superPow(base, prefix);
	part = modPow(part, 10, MODULUS);
	part = (part * modPow(base, lastDigit, MODULUS)) % MODULUS;
	return part;
}

function modPow(base, exponent, mod) {
	let result = 1;
	base = base % mod;
	while (exponent > 0) {
		if (exponent % 2 === 1) {
			result = (result * base) % mod;
		}
		base = (base * base) % mod;
		exponent = Math.floor(exponent / 2);
	}
	return result;
}