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
How to solve Amazon interview questions?
Does Meta use GitHub?
Which is better CodeChef or LeetCode or HackerRank?
Related Courses
Image
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.
Image
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Image
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.
;