Pow(x, n) - Fast Exponentiation

▶

Steps

setup

Check if exponent n is zero

The algorithm first checks if n is zero. If so, it returns 1 immediately because any number to the zero power is 1.

💡 This base case prevents unnecessary computation and handles the simplest input.

Line:

if n == 0:
    return 1.0

💡 Recognizing the zero exponent case is a fundamental base case in exponentiation.

setup

Handle negative exponent

The algorithm checks if n is negative to handle inversion later. Since n=10 is positive, it sets negative flag to false and keeps n as is.

💡 Handling negative exponents separately simplifies the main loop to only positive exponents.

Line:

negative = n < 0
n = abs(n)

💡 Separating sign handling allows the main loop to focus on positive exponent logic.

setup

Initialize result and current_product

Initialize result to 1.0 (identity for multiplication) and current_product to x (2.0). These will be updated during the loop.

💡 Starting with result=1 allows multiplication accumulation; current_product tracks powers of x.

Line:

result = 1.0
current_product = x

💡 Initialization sets the stage for iterative multiplication and squaring.

compare

Check least significant bit of n (bit 0)

Check if the least significant bit of n (10) is 1 by computing n % 2. Since 10 % 2 = 0, no multiplication occurs this iteration.

💡 Only multiply result by current_product when the current bit of n is 1.

Line:

if n % 2 == 1:
    result *= current_product

💡 This step shows how the algorithm selectively multiplies only when the bit is set.

expand

Square current_product

Square current_product: 2.0 * 2.0 = 4.0. This prepares the next power of x for the next bit of n.

💡 Squaring current_product moves to the next power of two exponent.

Line:

current_product *= current_product

💡 Squaring efficiently computes powers of x for each bit position.

shrink

Right shift n by 1 bit

Divide n by 2 using integer division: 10 // 2 = 5. This moves to the next bit of the exponent.

💡 Shifting n right moves through each bit from least to most significant.

Line:

n //= 2

💡 Reducing n by half each iteration ensures logarithmic time complexity.

compare

Check least significant bit of n (bit 1)

Check if n=5 has least significant bit 1: 5 % 2 = 1, so multiply result by current_product (1.0 * 4.0).

💡 When bit is 1, multiply accumulated result by current power.

Line:

if n % 2 == 1:
    result *= current_product

💡 This selective multiplication accumulates powers corresponding to set bits.

expand

Square current_product again

Square current_product: 4.0 * 4.0 = 16.0, preparing for next bit.

💡 Each iteration squares current_product to represent next power of two.

Line:

current_product *= current_product

💡 Squaring moves the base power forward exponentially.

shrink

Right shift n by 1 bit again

Divide n by 2: 5 // 2 = 2, moving to next bit.

💡 Shifting n right moves to next bit to process.

Line:

n //= 2

💡 Exponent bits are processed from least to most significant.

compare

Check least significant bit of n (bit 2)

Check if n=2 has least significant bit 1: 2 % 2 = 0, so skip multiplication.

💡 Only multiply when bit is set; here bit is 0 so no change to result.

Line:

if n % 2 == 1:
    result *= current_product

💡 Bits with zero do not contribute to the product.

expand

Square current_product again

Square current_product: 16.0 * 16.0 = 256.0 for next bit.

💡 Squaring prepares the base for the next higher bit.

Line:

current_product *= current_product

💡 Exponentiation by squaring is the core efficiency gain.

shrink

Right shift n by 1 bit again

Divide n by 2: 2 // 2 = 1, moving to last bit.

💡 Continue processing bits from least to most significant.

Line:

n //= 2

💡 Each iteration halves the exponent until zero.

compare

Check least significant bit of n (bit 3)

Check if n=1 has least significant bit 1: 1 % 2 = 1, multiply result by current_product (4.0 * 256.0).

💡 Final multiplication for the last set bit.

Line:

if n % 2 == 1:
    result *= current_product

💡 Multiplying at set bits accumulates the final power.

shrink

Right shift n by 1 bit to zero

Divide n by 2: 1 // 2 = 0, loop will end.

💡 Exponent fully processed when n reaches zero.

Line:

n //= 2

💡 Loop termination condition reached.

reconstruct

Return final result

Since original n was positive, return result as is: 1024.0.

💡 Final step returns the computed power.

Line:

return 1 / result if negative else result

💡 The algorithm completes with the correct power computed efficiently.

def myPow(x: float, n: int) -> float:
    # STEP 1
    if n == 0:
        return 1.0
    # STEP 2
    negative = n < 0
    n = abs(n)
    # STEP 3
    result = 1.0
    current_product = x
    # STEP 4-14
    while n > 0:
        # STEP 4
        if n % 2 == 1:
            result *= current_product  # STEP 7, 13
        # STEP 5, 8, 11
        current_product *= current_product
        # STEP 6, 9, 12, 14
        n //= 2
    # STEP 15
    return 1 / result if negative else result

📊

Pow(x, n) - Fast Exponentiation - Watch the Algorithm Execute, Step by Step

Watching each multiplication and bit-shift step reveals how the algorithm reduces the problem size exponentially, which is much faster than naive repeated multiplication.

compare

result

1

0

current_product

2

1

n

10

2

Result: 1

compare

result

1

0

current_product

2

1

n

10

2

Result: 1

setup

result

1

0

current_product

2

1

n

10

2

Result: 1

compare

result

1

0

current_product

2

1

n

10

2

Result: 1

expand

result

1

0

current_product

4

1

n

10

2

Result: 1

shrink

result

1

0

current_product

4

1

n

5

2

Result: 1

record

result

4

0

current_product

4

1

n

5

2

Result: 4

expand

result

4

0

current_product

16

1

n

5

2

Result: 4

shrink

result

4

0

current_product

16

1

n

2

2

Result: 4

compare

result

4

0

current_product

16

1

n

2

2

Result: 4

expand

result

4

0

current_product

256

1

n

2

2

Result: 4

shrink

result

4

0

current_product

256

1

n

1

2

Result: 4

record

result

1024

0

current_product

256

1

n

1

2

Result: 1024

shrink

result

1024

0

current_product

256

1

n

0

2

Result: 1024

return

result

1024

0

256

1

0

2

Result: 1024

Key Takeaways

✓ Binary exponentiation reduces the number of multiplications from n to O(log n) by processing bits of the exponent.

This efficiency is hard to see from code alone but becomes clear when watching each bit processed.

✓ The algorithm multiplies the result only when the current bit of n is 1, showing selective accumulation.

Visualizing this selective multiplication clarifies why some iterations update the result and others do not.

✓ Squaring current_product each iteration prepares the next power of x, demonstrating exponential growth of powers.

Seeing current_product grow exponentially helps understand why the algorithm is called 'exponentiation by squaring'.

Practice

1. You need to find the largest integer r such that r * r ≤ x for a given non-negative integer x. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Sorting all numbers and selecting the closest square root

B. Greedy approach incrementing from 0 until r * r > x

C. Dynamic programming to build up solutions for all numbers up to x

D. Modified binary search narrowing down the range of possible roots

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the integer square root efficiently without checking all numbers linearly.

2. Step 2: Identify the suitable algorithm

   Modified binary search efficiently narrows down the search space by comparing mid*mid with x, guaranteeing logarithmic time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search halves the search space each iteration [OK]

Hint: Binary search efficiently narrows down integer roots [OK]

Common Mistakes:

• Assuming greedy linear search is efficient
• Confusing DP with this problem
• Using sorting which is irrelevant

2. The following code attempts to find the k closest elements to x in a sorted array. Identify the line that contains a subtle bug that can cause incorrect results when distances tie.

medium

A. Line 7: mid = (low + high) // 2

B. Line 8: if abs(x - arr[mid]) > abs(arr[mid + k] - x):

C. Line 5: while low < high:

D. Line 10: return arr[low:low + k]

Solution

1. Step 1: Understand tie-breaker logic

   The problem requires choosing the smaller element when distances tie, but abs() removes sign information.

2. Step 2: Identify bug in distance comparison

   Using abs() ignores which side is closer and breaks tie-breaker rules, causing incorrect window selection.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct code compares x - arr[mid] and arr[mid+k] - x without abs [OK]

Hint: Tie-breakers require signed distance comparison, not absolute values [OK]

Common Mistakes:

• Using absolute values loses tie-breaker info
• Off-by-one errors in mid calculation
• Returning wrong slice boundaries

3. What is the time complexity of the optimal algorithm that finds the minimum element in a rotated sorted array without duplicates using modified binary search with neighbor checks?

medium

A. O(log n), because it halves the search space each iteration

B. O(log n * n), because neighbor checks add linear overhead each step

C. O(n), because in worst case it scans all elements

D. O(1), because it uses constant time comparisons

Solution

1. Step 1: Analyze loop behavior

   Each iteration halves the search space by adjusting left or right pointers based on comparisons.

2. Step 2: Neighbor checks are constant time

   Accessing prev and next indices uses modulo arithmetic, which is O(1), so no extra linear overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves array each iteration [OK]

Hint: Binary search halves search space, neighbor checks are O(1) [OK]

Common Mistakes:

• Confusing neighbor checks as linear scan
• Assuming linear time due to rotation
• Ignoring constant time modulo operations

4. What is the time complexity of the optimized binary search solution for placing m balls in n positions to maximize the minimum distance, where d is the maximum distance between the first and last positions?

medium

A. O(n log d)

B. O(n * d)

C. O(d log n)

D. O(n log n)

Solution

1. Step 1: Identify outer loop complexity

   Binary search on answer space runs in O(log d) iterations, where d is max distance.

2. Step 2: Identify inner loop complexity

   Each feasibility check scans positions once, O(n). Total complexity is O(n log d).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search x linear feasibility check = O(n log d) [OK]

Hint: Binary search on distance x linear feasibility check [OK]

Common Mistakes:

• Confusing d with n in complexity
• Assuming linear search over distances (O(n*d))

5. What is the time complexity of the optimal binary search algorithm that treats an m x n 2D matrix as a 1D sorted array to search for a target?

medium

A. O(log(m * n))

B. O(m * n)

C. O(m * log n)

D. O(log m + log n)

Solution

1. Step 1: Understand the search space size

   The matrix has m*n elements, treated as a sorted 1D array.

2. Step 2: Apply binary search complexity

   Binary search on an array of size m*n takes O(log(m*n)) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step, log scale [OK]

Hint: Binary search complexity depends on total elements, not rows or columns separately [OK]

Common Mistakes:

• Confusing with O(m*n) brute force
• Thinking binary search per row is O(m log n)
• Adding logs incorrectly as O(log m + log n)