Workspace

Problem workspace

3 day streakD

Exact Integer Nth Root

MediumBinary SearchNumbers & matrices

The challenge

Return an integer r with rᵖ = x, or −1 if no exact nonnegative integer root exists.

0 ≤ x ≤ 10⁹ and 1 ≤ p ≤ 31. Return 0 for x = 0.

Example

x = 27, p = 3 → 3; x = 28, p = 3 → −1.

Use the walkthrough below to inspect the input and each state change.

See Nth root, step by step

Inspect the comparison, the invariant, and the next boundary.

Answer-space searchx = 27 · p = 3
left1candidate—right27Search candidate values, not input indices
Tested candidate / qualifying inputResolved positionParameters shown above
Left
1
Middle
—
Right
27
Step 01 / 5

Search the answer range

The candidate is a number, rather than an input index. Require an exact power match.

left = 1; right = 27

Recorded result so far

Not resolved
View exact input

Input: [] · x = 27 · p = 3

Put it into code

Binary search candidate roots. Build the power with a guard before every multiplication and stop as soon as it would exceed x.

Indices are zero-based. C++ uses C++17 or later.

def nth_root(x, p):
    # 0 <= x <= 10**9; 1 <= p <= 31.
    if x == 0:
        return 0
    left, right = 1, x
    while left <= right:
        mid = left + (right - left) // 2
        power = 1
        for _ in range(p):
            if power > x // mid:
                power = x + 1
                break
            power *= mid
        if power == x:
            return mid
        if power < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap