Pow(x, n) Solution in Java

Language Options

Problem Description

So, you want to calculate xⁿ (that’s x raised to the power of n) without breaking a sweat? Welcome to the world of LeetCode, where we solve problems that make you question your life choices! Imagine you’re trying to figure out how many times you can double your money before your bank account starts crying. That’s basically what this problem is about, but with numbers instead of dollars.

In this problem, you need to implement a function that takes a double x and an integer n and returns xⁿ. Easy, right? Well, hold on! What if n is negative? Or zero? Or a huge number? Don’t worry; we’ve got you covered!

Code Solution


class Solution {
  public double myPow(double x, long n) {
    if (n == 0)
      return 1;
    if (n < 0)
      return 1 / myPow(x, -n);
    if (n % 2 == 1)
      return x * myPow(x, n - 1);
    return myPow(x * x, n / 2);
  }
}

Approach

The approach used in this code is a classic example of divide and conquer. The function checks if n is zero (in which case it returns 1, because anything raised to the power of zero is 1). If n is negative, it flips the problem around by calculating x^-n. If n is odd, it multiplies x by the result of x^n-1. If n is even, it squares x and halves n, effectively reducing the problem size significantly with each recursive call.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(log n)
Space Complexity	O(log n)

Real-World Example

Imagine you’re a baker trying to figure out how many cupcakes you can make if you double the recipe every time. If you start with one cupcake and double it n times, you can use this function to calculate how many cupcakes you’ll have at the end. Just remember, if you double too many times, you might end up with a mountain of cupcakes that could feed a small army!