Math Algorithms: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Math Algorithms: Complete Guide with Worked Examples

Welcome to the practice problems for math algorithms. If you need the primitives fresh, the code templates have the Euclidean GCD, fast exponentiation, and the sieve in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems build from digit mechanics to full number theory. Reverse Integer and Palindrome Number teach the digit-by-digit loop that shows up in almost every pure-math question. Count Primes exercises the sieve, and Pow(x, n) exercises fast exponentiation. Factorial Trailing Zeroes and Water and Jug Problem are the insight problems: each one hides a short number-theory argument behind an ordinary-looking question. Super Pow, the Hard problem, combines modular exponentiation with an exponent that does not fit in any integer type, so it pulls together everything earlier in the list.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Reverse Integer

LeetCode 7 | Difficulty: Easy

Brief: Given a 32-bit signed integer, return its digits reversed. Return 0 if the reversed value would fall outside the 32-bit range.

Why this pattern: Digit extraction with repeated modulo and division is the most basic math primitive. The overflow guard is what makes this a real interview question instead of a toy.

Hint: Check the overflow condition before you append the next digit, not after. By the time the value has grown past the limit, it is already corrupted.

Visual:

    graph TD
    A["x = 123"] --> B["digit = 3, x = 12"]
    B --> C["rev = 3"]
    C --> D["digit = 2, x = 1"]
    D --> E["rev = 32"]
    E --> F["digit = 1, x = 0"]
    F --> G["rev = 321"]

Code:

function reverse(x) {
    const INT_MAX = 2147483647;
    const INT_MIN = -2147483648;
    let rev = 0;

    while (x !== 0) {
        const digit = x % 10;
        x = Math.trunc(x / 10);

        // Check before appending: once rev grows past the
        // 32-bit limit there is no way to recover
        if (rev > Math.trunc(INT_MAX / 10) || (rev === Math.trunc(INT_MAX / 10) && digit > 7)) return 0;
        if (rev < Math.trunc(INT_MIN / 10) || (rev === Math.trunc(INT_MIN / 10) && digit < -8)) return 0;

        rev = rev * 10 + digit;
    }

    return rev;
}

def reverse(x: int) -> int:
    # Python's modulo returns a non-negative remainder for
    # negative inputs, so peel digits off the absolute value
    # and reapply the sign at the end
    sign = -1 if x < 0 else 1
    x = abs(x)
    rev = 0

    while x > 0:
        digit = x % 10
        x //= 10
        rev = rev * 10 + digit

    rev *= sign
    return rev if -(2**31) <= rev <= 2**31 - 1 else 0

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int digit = x % 10;
            x /= 10;

            // Overflow check must run before the append,
            // because the multiplication is what breaks the limit
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && digit < -8)) return 0;

            rev = rev * 10 + digit;
        }
        return rev;
    }
}

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int digit = x % 10;
            x /= 10;

            // Check before appending, because the
            // multiplication is what breaks the limit
            if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && digit > 7)) return 0;
            if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && digit < -8)) return 0;

            rev = rev * 10 + digit;
        }
        return rev;
    }
};

func reverse(x int) int {
    const INT_MAX = 2147483647
    const INT_MIN = -2147483648
    rev := 0

    for x != 0 {
        digit := x % 10
        x /= 10

        // Check before appending, because the
        // multiplication is what breaks the limit
        if rev > INT_MAX/10 || (rev == INT_MAX/10 && digit > 7) {
            return 0
        }
        if rev < INT_MIN/10 || (rev == INT_MIN/10 && digit < -8) {
            return 0
        }

        rev = rev*10 + digit
    }

    return rev
}

def reverse(x)
    # Ruby's modulo returns a non-negative remainder for
    # negative inputs, so peel digits off the absolute value
    # and reapply the sign at the end
    sign = x.negative? ? -1 : 1
    x = x.abs
    rev = 0

    while x > 0
        digit = x % 10
        x /= 10
        rev = rev * 10 + digit
    end

    rev *= sign
    rev.between?(-2**31, 2**31 - 1) ? rev : 0
end

The overflow checks compare against INT_MAX / 10 before multiplying, and the digit clauses handle the exact boundary where the last digit pushes past the range. Python and Ruby do not overflow, so there you compute first and check the range at the end. Java, C++, Go, and JavaScript truncate negative division toward zero, which makes x % 10 and x / 10 agree on digit extraction, so no sign handling is needed there.

Time

O(log N)

| Space

O(1)

2. Palindrome Number

LeetCode 9 | Difficulty: Easy

Brief: Determine whether an integer is a palindrome without converting it to a string.

Why this pattern: Reversing only half of the number with the same digit-extraction loop avoids rebuilding the whole integer, which could overflow on large inputs.

Hint: Stop the loop once the reversed half grows past the remaining half. The middle digit of an odd-length number takes care of itself.

Visual:

    graph TD
    A["x = 1221"] --> B["rev = 1, x = 122"]
    B --> C["rev = 12, x = 12"]
    C --> D["x <= rev, compare"]
    D --> E["12 == 12, true"]

Code:

function isPalindrome(x) {
    // Negative numbers and any positive number ending
    // in 0 can never read the same backwards
    if (x < 0 || (x % 10 === 0 && x !== 0)) {
        return false;
    }

    let rev = 0;
    while (x > rev) {
        rev = rev * 10 + x % 10;
        x = Math.floor(x / 10);
    }

    // Even length: x == rev. Odd length: the middle
    // digit sits on top of rev, so drop it with /10.
    return x === rev || x === Math.floor(rev / 10);
}

def is_palindrome(x: int) -> bool:
    # Negative numbers and any positive number ending
    # in 0 can never read the same backwards
    if x < 0 or (x % 10 == 0 and x != 0):
        return False

    rev = 0
    while x > rev:
        rev = rev * 10 + x % 10
        x //= 10

    # Even length: x == rev. Odd length: the middle
    # digit sits on top of rev, so drop it with // 10.
    return x == rev or x == rev // 10

class Solution {
    public boolean isPalindrome(int x) {
        // Negative numbers and any positive number ending
        // in 0 can never read the same backwards
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }

        // Even length: x == rev. Odd length: the middle
        // digit sits on top of rev, so drop it with / 10.
        return x == rev || x == rev / 10;
    }
}

class Solution {
public:
    bool isPalindrome(int x) {
        // Negative numbers and any positive number ending
        // in 0 can never read the same backwards
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }

        // Even length: x == rev. Odd length: the middle
        // digit sits on top of rev, so drop it with / 10.
        return x == rev || x == rev / 10;
    }
};

func isPalindrome(x int) bool {
    // Negative numbers and any positive number ending
    // in 0 can never read the same backwards
    if x < 0 || (x%10 == 0 && x != 0) {
        return false
    }

    rev := 0
    for x > rev {
        rev = rev*10 + x%10
        x /= 10
    }

    // Even length: x == rev. Odd length: the middle
    // digit sits on top of rev, so drop it with /10.
    return x == rev || x == rev/10
}

def is_palindrome(x)
    # Negative numbers and any positive number ending
    # in 0 can never read the same backwards
    return false if x < 0 || (x % 10 == 0 && x != 0)

    rev = 0
    while x > rev
        rev = rev * 10 + x % 10
        x /= 10
    end

    # Even length: x == rev. Odd length: the middle
    # digit sits on top of rev, so drop it with / 10.
    x == rev || x == rev / 10
end

The early return for negative numbers and numbers ending in 0 is required, because the half-reversal loop assumes the input still has digits left to compare. When the loop ends, x holds the first half and rev holds the reversed second half. Odd-length inputs leave the middle digit on top of rev, so comparing x == rev / 10 handles both lengths with one condition.

Time

O(log N)

| Space

O(1)

Medium Problems

3. Count Primes

LeetCode 204 | Difficulty: Medium

Brief: Count the number of primes strictly less than n.

Why this pattern: Checking each number individually costs too much across a large range. The Sieve of Eratosthenes marks every composite once and counts the survivors in a single pass.

Hint: The sieve only needs to run up to sqrt(n). Every composite below n has a prime factor at or below sqrt(n).

Visual:

    graph TD
    A["n = 10"] --> B["Mark 4, 6, 8 with 2"]
    B --> C["Mark 9 with 3"]
    C --> D["Survivors: 2, 3, 5, 7"]
    D --> E["Answer: 4"]

Code:

function countPrimes(n) {
    if (n <= 2) return 0;

    const isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;

    // A composite below n always has a prime factor
    // at or below sqrt(n), so the marking pass stops there
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            // Start at i*i: smaller multiples were already
            // marked by a smaller prime factor
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime.filter(Boolean).length;
}

def count_primes(n: int) -> int:
    if n <= 2:
        return 0

    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False

    i = 2
    while i * i < n:
        if is_prime[i]:
            # Start at i*i: smaller multiples were already
            # marked by a smaller prime factor
            for j in range(i * i, n, i):
                is_prime[j] = False
        i += 1

    return sum(is_prime)

import java.util.Arrays;

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;

        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        // A composite below n always has a prime factor
        // at or below sqrt(n), so the marking pass stops there
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                // Smaller multiples of i are already marked,
                // so the loop starts at i*i
                for (long j = (long) i * i; j < n; j += i) {
                    isPrime[(int) j] = false;
                }
            }
        }

        int count = 0;
        for (boolean prime : isPrime) {
            if (prime) count++;
        }
        return count;
    }
}

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0;

        vector<bool> is_prime(n, true);
        is_prime[0] = is_prime[1] = false;

        // A composite below n always has a prime factor
        // at or below sqrt(n), so the marking pass stops there
        for (int i = 2; i * i < n; i++) {
            if (is_prime[i]) {
                // Start at i*i: smaller multiples are
                // already marked by smaller primes
                for (long long j = (long long)i * i; j < n; j += i) {
                    is_prime[j] = false;
                }
            }
        }

        int count = 0;
        for (bool prime : is_prime) {
            if (prime) count++;
        }
        return count;
    }
};

func countPrimes(n int) int {
    if n <= 2 {
        return 0
    }

    isPrime := make([]bool, n)
    for i := range isPrime {
        isPrime[i] = true
    }
    isPrime[0], isPrime[1] = false, false

    // A composite below n always has a prime factor
    // at or below sqrt(n), so the marking pass stops there
    for i := 2; i*i < n; i++ {
        if isPrime[i] {
            // Start at i*i: smaller multiples are
            // already marked by smaller primes
            for j := i * i; j < n; j += i {
                isPrime[j] = false
            }
        }
    }

    count := 0
    for _, prime := range isPrime {
        if prime {
            count++
        }
    }
    return count
}

def count_primes(n)
    return 0 if n <= 2

    is_prime = Array.new(n, true)
    is_prime[0] = is_prime[1] = false

    # A composite below n always has a prime factor
    # at or below sqrt(n), so the marking pass stops there
    i = 2
    while i * i < n
        if is_prime[i]
            # Start at i*i: smaller multiples are
            # already marked by smaller primes
            j = i * i
            while j < n
                is_prime[j] = false
                j += i
            end
        end
        i += 1
    end

    is_prime.count(true)
end

The guard n <= 2 handles the empty cases so the array never gets indexed out of range. The boundary is “less than n”, so the array has size n and 1 is marked as not prime before the loop. The inner loop starts at i*i because smaller multiples already got marked by a smaller factor, which is what keeps the total work around N log log N instead of N sqrt(N).

Time

O(N log log N)

| Space

O(N)

4. Pow(x, n)

LeetCode 50 | Difficulty: Medium

Brief: Implement pow(x, n) for a float base and an integer exponent, which may be negative.

Why this pattern: This is fast exponentiation directly. Multiplying x by itself n times is O(N). Squaring the base and halving the exponent is O(log N).

Hint: For a negative exponent, invert the base and negate the exponent once, then run the squaring loop.

Visual:

    graph TD
    A["2^10"] --> B["res = 1, base = 2, exp = 10"]
    B --> C["exp even: base = 4, exp = 5"]
    C --> D["exp odd: res = 4, base = 16, exp = 2"]
    D --> E["exp even: base = 256, exp = 1"]
    E --> F["exp odd: res = 1024, exp = 0"]
    F --> G["return 1024"]

Code:

function myPow(x, n) {
    // A negative exponent means the reciprocal,
    // so invert the base and flip the exponent
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }

    let result = 1;
    while (n > 0) {
        // When the current bit of the exponent is set,
        // the running base belongs in the result
        if (n % 2 === 1) result *= x;
        x *= x;
        n = Math.floor(n / 2);
    }
    return result;
}

def my_pow(x: float, n: int) -> float:
    # A negative exponent means the reciprocal,
    # so invert the base and flip the exponent
    if n < 0:
        x = 1 / x
        n = -n

    result = 1.0
    while n > 0:
        # When the current bit of the exponent is set,
        # the running base belongs in the result
        if n % 2 == 1:
            result *= x
        x *= x
        n //= 2
    return result

class Solution {
    public double myPow(double x, int n) {
        // Negating n on a 64-bit copy avoids overflowing
        // on the minimum 32-bit value
        long exp = n;
        if (exp < 0) {
            x = 1 / x;
            exp = -exp;
        }

        double result = 1.0;
        while (exp > 0) {
            // When the current bit of the exponent is set,
            // the running base belongs in the result
            if (exp % 2 == 1) result *= x;
            x *= x;
            exp /= 2;
        }
        return result;
    }
}

class Solution {
public:
    double myPow(double x, int n) {
        // Negating n on a 64-bit copy avoids overflowing
        // on the minimum 32-bit value
        long long exp = n;
        if (exp < 0) {
            x = 1 / x;
            exp = -exp;
        }

        double result = 1.0;
        while (exp > 0) {
            // When the current bit of the exponent is set,
            // the running base belongs in the result
            if (exp % 2 == 1) result *= x;
            x *= x;
            exp /= 2;
        }
        return result;
    }
};

func myPow(x float64, n int) float64 {
    // Negating n on a 64-bit copy avoids overflowing
    // on the minimum 32-bit value
    exp := int64(n)
    if exp < 0 {
        x = 1 / x
        exp = -exp
    }

    result := 1.0
    for exp > 0 {
        // When the current bit of the exponent is set,
        // the running base belongs in the result
        if exp%2 == 1 {
            result *= x
        }
        x *= x
        exp /= 2
    }
    return result
}

def my_pow(x, n)
    # A negative exponent means the reciprocal,
    # so invert the base and flip the exponent
    if n.negative?
        x = 1.0 / x
        n = -n
    end

    result = 1.0
    while n > 0
        # When the current bit of the exponent is set,
        # the running base belongs in the result
        result *= x if n.odd?
        x *= x
        n /= 2
    end
    result
end

The loop reads the exponent bit by bit. When a bit is set, the current power contributes to the result, and every iteration squares the base regardless. That doubling is why the loop runs about log2(n) times instead of n. Fixed-width languages copy the exponent to 64 bits before negating, because negating the 32-bit minimum value overflows and stays negative.

Time

O(log N)

| Space

O(1)

5. Factorial Trailing Zeroes

LeetCode 172 | Difficulty: Medium

Brief: Return the number of trailing zeros in n!.

Why this pattern: This is a pure number-theory insight problem. A trailing zero needs a factor of 10, which needs a 2 and a 5. Twos are plentiful in a factorial, so the answer is the count of factors of 5.

Hint: Count the multiples of 5, then 25, then 125. Each successive power of 5 adds one more factor of 5 to the total.

Visual:

    graph TD
    A["n = 25"] --> B["Multiples of 5: 5, 10, 15, 20, 25"]
    B --> C["Count: 5"]
    A --> D["Multiples of 25: 25"]
    D --> E["Count: 1"]
    C --> F["Total: 6"]
    E --> F

Code:

function trailingZeroes(n) {
    let count = 0;
    // Each power of 5 contributes one more factor of 5
    // to the total, so keep dividing n by 5
    while (n >= 5) {
        n = Math.floor(n / 5);
        count += n;
    }
    return count;
}

def trailing_zeroes(n: int) -> int:
    count = 0
    # Each power of 5 contributes one more factor of 5
    # to the total, so keep dividing n by 5
    while n >= 5:
        n //= 5
        count += n
    return count

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        // Each power of 5 contributes one more factor of 5
        // to the total, so keep dividing n by 5
        while (n >= 5) {
            n /= 5;
            count += n;
        }
        return count;
    }
}

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        // Each power of 5 contributes one more factor of 5
        // to the total, so keep dividing n by 5
        while (n >= 5) {
            n /= 5;
            count += n;
        }
        return count;
    }
};

func trailingZeroes(n int) int {
    count := 0
    // Each power of 5 contributes one more factor of 5
    // to the total, so keep dividing n by 5
    for n >= 5 {
        n /= 5
        count += n
    }
    return count
}

def trailing_zeroes(n)
    count = 0
    # Each power of 5 contributes one more factor of 5
    # to the total, so keep dividing n by 5
    while n >= 5
        n /= 5
        count += n
    end
    count
end

The loop divides n by 5 and adds each quotient. For n = 25 that is 25/5 = 5 plus 25/25 = 1, for a total of 6, because 25 itself contributes two factors of 5. The repeated division is what catches every power of 5, and it runs about log5(n) times, which keeps even very large factorials in range without ever computing the factorial itself.

Time

O(log N)

| Space

O(1)

6. Water and Jug Problem

LeetCode 365 | Difficulty: Medium

Brief: With jugs of capacity x and y, decide whether you can measure exactly target liters.

Why this pattern: Every amount you can measure is a linear combination of the two capacities, and the achievable amounts are exactly the multiples of gcd(x, y). Bezout’s identity is doing the work here, and the Euclidean GCD template is the whole solution.

Hint: Check that target is a multiple of gcd(x, y) and not larger than the sum of the two capacities.

Visual:

    graph TD
    A["x = 3, y = 5, target = 4"] --> B["gcd(3, 5) = 1"]
    B --> C["4 is a multiple of 1"]
    C --> D["4 <= 3 + 5"]
    D --> E["Measurable: true"]

Code:

function canMeasureWater(x, y, target) {
    if (x + y < target) return false;
    // Both jugs empty can only measure zero
    if (x + y === 0) return target === 0;

    const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
    // Every measurable amount is a multiple of the GCD
    return target % gcd(x, y) === 0;
}

import math

def can_measure_water(x: int, y: int, target: int) -> bool:
    if x + y < target:
        return False
    # Both jugs empty can only measure zero
    if x + y == 0:
        return target == 0
    # Every measurable amount is a multiple of the GCD
    return target % math.gcd(x, y) == 0

class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        if ((long) x + y < target) return false;
        // Both jugs empty can only measure zero
        if (x + y == 0) return target == 0;
        return target % gcd(x, y) == 0;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

class Solution {
public:
    bool canMeasureWater(int x, int y, int target) {
        if ((long long)x + y < target) return false;
        // Both jugs empty can only measure zero
        if (x + y == 0) return target == 0;
        return target % gcd(x, y) == 0;
    }

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

func canMeasureWater(x int, y int, target int) bool {
    if x+y < target {
        return false
    }
    // Both jugs empty can only measure zero
    if x+y == 0 {
        return target == 0
    }
    return target%gcd(x, y) == 0
}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

Pouring between two jugs keeps the total amount constant except when a jug is emptied or filled, so the reachable amounts are exactly the multiples of the GCD up to the combined capacity. The sum check bounds the total, and the empty case needs its own guard so the modulo never divides by zero. Java and C++ widen the sum before comparing because the capacities can approach the 32-bit limit.

Time

O(log N)

| Space

O(1)

(N is the smaller capacity)

Hard Problems

7. Super Pow

LeetCode 372 | Difficulty: Hard

Brief: Compute a^b mod 1337, where the exponent b is given as an array of decimal digits.

Why this pattern: The exponent does not fit in any integer type, so the squaring loop cannot take it directly. Processing digits left to right, each digit shifts the running result one decimal place left, and modular exponentiation keeps every value bounded.

Hint: After each digit, raise the running result to the 10th power and multiply in a^digit, all modulo 1337.

Visual:

    graph TD
    A["a = 2, b = [1, 0]"] --> B["digit 1: result = 2^1 = 2"]
    B --> C["digit 0: result = 2^10 mod 1337"]
    C --> D["2^10 = 1024"]
    D --> E["Answer: 1024"]

Code:

function superPow(a, b) {
    const MOD = 1337;

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

    let result = 1;
    for (const digit of b) {
        // Appending a digit multiplies the exponent by 10,
        // so raise the running result to 10 and add a^digit
        result = modPow(result, 10) * modPow(a, digit) % MOD;
    }
    return result;
}

def super_pow(a: int, b: List[int]) -> int:
    MOD = 1337

    def mod_pow(base: int, exp: int) -> int:
        result = 1
        base %= MOD
        while exp > 0:
            if exp % 2 == 1:
                result = result * base % MOD
            base = base * base % MOD
            exp //= 2
        return result

    result = 1
    for digit in b:
        # Appending a digit multiplies the exponent by 10,
        # so raise the running result to 10 and add a^digit
        result = mod_pow(result, 10) * mod_pow(a, digit) % MOD
    return result

class Solution {
    private int modPow(int base, int exp) {
        int result = 1;
        base %= 1337;
        while (exp > 0) {
            if (exp % 2 == 1) result = result * base % 1337;
            base = base * base % 1337;
            exp /= 2;
        }
        return result;
    }

    public int superPow(int a, int[] b) {
        int result = 1;
        for (int digit : b) {
            // Appending a digit multiplies the exponent by 10,
            // so raise the running result to 10 and add a^digit
            result = modPow(result, 10) * modPow(a, digit) % 1337;
        }
        return result;
    }
}

class Solution {
public:
    int modPow(int base, int exp) {
        int result = 1;
        base %= 1337;
        while (exp > 0) {
            if (exp % 2 == 1) result = result * base % 1337;
            base = base * base % 1337;
            exp /= 2;
        }
        return result;
    }

    int superPow(int a, vector<int>& b) {
        int result = 1;
        for (int digit : b) {
            // Appending a digit multiplies the exponent by 10,
            // so raise the running result to 10 and add a^digit
            result = modPow(result, 10) * modPow(a, digit) % 1337;
        }
        return result;
    }
};

func superPow(a int, b []int) int {
    const mod = 1337

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

    result := 1
    for _, digit := range b {
        // Appending a digit multiplies the exponent by 10,
        // so raise the running result to 10 and add a^digit
        result = modPow(result, 10) * modPow(a, digit) % mod
    }
    return result
}

def super_pow(a, b)
    mod = 1337

    mod_pow = ->(base, exp) {
        result = 1
        base %= mod
        while exp > 0
            result = result * base % mod if exp.odd?
            base = base * base % mod
            exp /= 2
        end
        result
    }

    result = 1
    b.each do |digit|
        # Appending a digit multiplies the exponent by 10,
        # so raise the running result to 10 and add a^digit
        result = mod_pow.call(result, 10) * mod_pow.call(a, digit) % mod
    end
    result
end

Reading digits left to right, appending digit d turns the exponent from e into 10e + d, so the result transforms from a^e into (a^e)^10 * a^d. Raising the running result to the 10th power uses the same squaring loop from the template, and taking the modulo at every multiply keeps the values small enough for any language. The exponent never exists as a number, which is the point of the problem.

Time

O(N)

| Space

O(1)

(N is the number of digits)

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These seven problems cover the full range of math algorithms. Start with digit manipulation in Reverse Integer and Palindrome Number, move to the two workhorse primitives in Count Primes and Pow(x, n), then test your number-theory instincts on Factorial Trailing Zeroes and Water and Jug Problem. Super Pow is the capstone: it combines modular exponentiation with an exponent that only exists as digits, so it exercises everything above.

Done with these problems? The app has more, plus a review system that brings problems back right before you would forget them. Continue your prep .