50. Pow(x, n) - Detailed Explanation

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Implement a function to calculate x raised to the power n, i.e., compute xⁿ. Note that n can be negative, and the result should be returned as a double.

Example 1:

  • Input: x = 2.00000, n = 10
  • Output: 1024.00000
  • Explanation: 2¹⁰ = 1024

Example 2:

  • Input: x = 2.10000, n = 3
  • Output: 9.26100
  • Explanation: 2.1³ ≈ 9.261

Example 3:

  • Input: x = 2.00000, n = -2
  • Output: 0.25000
  • Explanation: 2⁻² = 1/(2²) = 0.25

Constraints:

  • -100.0 < x < 100.0
  • -2³¹ ≤ n ≤ 2³¹ - 1
  • n is an integer
  • xⁿ will be in the range of a double

Hints and Key Ideas

  • Handling Negative Exponents:
    If n is negative, compute the power for the positive exponent and then take the reciprocal (i.e., result = 1 / (x^(-n))).

  • Brute Force vs. Fast Exponentiation:
    A simple solution might multiply x by itself n times, but when n is large, this approach becomes inefficient. Instead, using the divide-and-conquer technique (also known as exponentiation by squaring) reduces the number of multiplications significantly.

Approaches

Approach 1: Brute Force Multiplication

Explanation:

The brute force approach simply multiplies x by itself n times.

  • For Positive n: Loop n times and multiply.
  • For Negative n: Compute x^|n| and return its reciprocal.
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Python Code (Brute Force):

Python3
Python3

. . . .

Java Code (Brute Force):

Java
Java

. . . .

Approach 2: Fast Exponentiation (Divide and Conquer)

Explanation:

The fast exponentiation method (or exponentiation by squaring) reduces the number of multiplications by using the following logic:

  • If n is 0: Return 1.
  • Recursively compute:
    • Let half = x^(n//2).
    • If n is even, then xⁿ = half * half.
    • If n is odd, then xⁿ = half * half * x.
  • For negative n: Convert the problem into computing x^|n| and then return the reciprocal.
  • Time Complexity: O(log n)
  • Space Complexity: O(log n) due to recursion stack (or O(1) in an iterative version)

Python Code (Fast Exponentiation):

Python3
Python3

. . . .

Java Code (Fast Exponentiation):

Java
Java

. . . .

Final Thoughts

Edge Cases:

  • n = 0: Any number raised to the power 0 is 1.
  • Negative Exponents: The method should correctly handle negative exponents by computing the positive power and taking the reciprocal.
  • Large Exponents: The fast exponentiation approach efficiently handles large values of n using O(log n) multiplications.

Common Pitfalls:

  • Overflow: In languages like Java, converting n to a long when taking the absolute value can avoid overflow issues when n is Integer.MIN_VALUE.
  • Precision: Floating-point arithmetic might lead to precision issues, so be cautious in scenarios requiring very high precision.
TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
Related Courses
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.
;