Frontend School

Calculate Power (x^n)

DSA
easy

Calculate Power (x^n)

Easy
Math
Recursion
Divide and Conquer

Overview

Efficiently calculating powers is a fundamental operation in computer science, underpinning various algorithms from cryptography to numerical analysis. A naive multiplication approach can be prohibitively slow for large exponents. This problem challenges you to implement an optimized power function using a Divide and Conquer strategy.

What you need to do / Task

Implement the myPow(x, n) function, which calculates x raised to the power n.

Your solution should:

  1. Use a Divide and Conquer approach (also known as exponentiation by squaring).
  2. Handle all specified constraints and edge cases efficiently.

Input & output

Function Signature: function myPow(x: number, n: number): number

Parameters:

  • x: A number (float) representing the base.
  • n: A non-negative number (integer) representing the exponent.

Return Value:

  • A number representing x raised to the power n (x^n).

Clarifications

  • n will always be a non-negative integer.
  • For x = 0 and n = 0, the result should be 1.0 (following common programming library conventions like Math.pow(0, 0)).
  • The problem focuses on the algorithmic approach rather than extreme floating-point precision challenges. Standard number type precision is sufficient.

Examples

1

Example 1

Input:

x = 2.00000, n = 10

Output:

1024.00000

Note:

2^10 = 1024

2

Example 2

Input:

x = 2.10000, n = 3

Output:

9.26100

Note:

2.1^3 = 9.261

3

Example 3

Input:

x = 0.00000, n = 0

Output:

1.00000

Note:

By convention, 0^0 is 1.

4

Example 4

Input:

x = 1.00000, n = 1000000

Output:

1.00000

Note:

1 raised to any power is 1.

Constraints

Constraints & assumptions

  • -100.0 < x < 100.0
  • 0 <= n <= 10^9
  • The final result is guaranteed to be within the range [-10^9, 10^9] and can be accurately represented by a standard double-precision floating-point number.
  • Your solution should aim for O(log n) time complexity.
  • Your solution should aim for O(log n) space complexity (due to recursion stack) or O(1) if an iterative approach is used.

Out of scope

  • Handling negative exponents (n < 0).
  • Handling non-integer exponents.
  • Arbitrary precision arithmetic for extremely large results or exponents.

What interviewers evaluate

  • Algorithmic Correctness: Correctly applies the Divide and Conquer paradigm for exponentiation.
  • Edge Case Handling: Properly addresses base cases like n=0 and x=0.
  • Efficiency: Achieves the optimal O(log n) time complexity.
  • Code Quality: Writes clean, readable, and well-structured code.

Loading editor...