Implement Power Function
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Implement Power Function * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Implement Power Function (Modular Exponentiation) * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Implement a function to calculate (A^B) % C. * The function must ensure that the returned remainder is non-negative, even if A is negative. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let F(A, B, C) be the function that calculates (A^B) % C. * * Naive Approach: * Computing A^B iteratively takes O(B) time. With B <= 10^9, this will cause a * Time Limit Exceeded (TLE). We must use "Divide and Conquer" (Binary Exponentiation). * * Recurrence Relation: * 1. Calculate half-power: T = F(A, B/2, C) * 2. If B is even: * F(A, B, C) = (T * T) % C * 3. If B is odd: * F(A, B, C) = (A * T * T) % C * * Base Case: * If A == 0 : Return 0 (0^B is 0, provided B > 0) * If B == 0 : Return 1 (Any number^0 is 1) * * --------------------- * 3. Constraints & Optimization * --------------------- * Constraints: * -10^9 <= A <= 10^9 (Base can be negative!) * 0 <= B <= 10^9 (Exponent is large -> requires O(log B)) * 1 <= C <= 10^9 * * Optimization (Critical): * 1. Time Complexity: O(log B). We halve B at every step. * 2. Space Complexity: O(log B) for recursion stack. * * Critical Implementation Details: * 1. Data Type Overflow: * Intermediate calculations like (T * T) can reach approx (10^9)^2 = 10^18. * This exceeds the range of a 32-bit 'int'. You MUST use 'long' for intermediate products. * * 2. Negative Bases: * In Java, the % operator returns a negative remainder if the dividend is negative * (e.g., -2 % 3 = -2). * The problem requires a non-negative result. * Fix: result = (result % C + C) % C * * --------------------- * 4. Input / Output Format * --------------------- * Input: Three integers A, B, C. * Output: Integer result of (A^B) % C. * * --------------------- * 5. Examples * --------------------- * Input 1: A=2, B=3, C=3 * Output 1: 2 * Explanation: 2^3 = 8. 8 % 3 = 2. * * Input 2: A=-1, B=1, C=20 * Output 2: 19 * Explanation: (-1)^1 = -1. -1 % 20 = -1. Non-negative adjustment: -1 + 20 = 19. * * ============================================================================================ */ public class ImplementPowerFunction { public int solve(int A) { // TODO: Implement solution return 0; }
public int pow(int i, int i1, int i2) {
return 1;
}
}