CodingGyan

Power Without a Library Method

medium Programming Basics

Problem

Read a base and an exponent (a non-negative whole number) and print base to the power of exponent. Do not use Math.pow, the ** operator or pow(). The result fits in a 53-bit integer, except for base 1 and base 0.

Constraints

  • 0 <= base <= 10^9, 0 <= exponent <= 10^9 (the result must be small enough)

Examples

Input

2 10

Output

1024

Solutions

Best approachTime O(log exponent)Space O(1)

x^8 = (x^2)^4 = ((x^2)^2)^2. We halve the exponent each time and square the base, and we multiply the result only when the exponent is odd. This needs about log2(exponent) steps.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Calculate base to the power exponent without a library method.
 * Input   : Two integers: base and exponent (exponent >= 0).
 * Output  : base^exponent.
 * Approach: Square the base and halve the exponent (fast exponentiation).
 * Time    : O(log exponent)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long base = scanner.nextLong();
        long exponent = scanner.nextLong();

        // Step 1: The result starts at 1.
        long result = 1;

        // Step 2: Repeat until the exponent is 0.
        while (exponent > 0) {
            // Step 3: If the exponent is odd, multiply the result by the current base once.
            if (exponent % 2 == 1) {
                result = result * base;
            }

            // Step 4: Square the base and halve the exponent. Example: 3^8 = 9^4 = 81^2 = 6561^1.
            base = base * base;
            exponent = exponent / 2;
        }

        // Step 5: Print the result.
        System.out.println(result);
    }
}
Hints (2)
  1. What is 3^8 if you know 3^4?
  2. What do you do when the exponent is odd?

Try these next