CodingGyan

Power with Recursion (Divide by Two)

medium Recursion and Backtracking

Problem

Read a base and an exponent (exponent >= 0). Print base to the power of exponent using recursion that halves the exponent each time. The result is smaller than 2^53 (except for base 1 and 0).

Constraints

  • 0 <= base <= 10^9, 0 <= exponent <= 10^6, the result < 2^53

Examples

Input

2 10

Output

1024

Solutions

Best approachTime O(log b)Space O(log b)

a^b = (a^(b/2))^2, and one more factor a when b is odd. We call the function only once for the half problem, so the depth is log2(b). If we called it twice, the time would grow back to O(b).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Compute a power.
 * Input   : Base and exponent.
 * Output  : The power.
 * Approach: Halve the exponent.
 * Time    : O(log b)
 * Space   : O(log b)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long a, long b) {
        // Step 1: Base case. Any number to the power 0 is 1.
        if (b == 0) {
            return 1;
        }

        // Step 2: Solve the half problem once. Example: 2^10 needs 2^5.
        long half = solve(a, b / 2);

        // Step 3: Two halves make the whole. If the exponent is odd, multiply by the base one more time.
        if (b % 2 == 0) {
            return half * half;
        }
        return half * half * a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        System.out.println(solve(a, b));
    }
}
Hints (1)
  1. Why must the half result be stored in a variable?

Try these next