Rabbit Counter Wraparound

EasyrecursionAlso known as Pow(x, n) / Modular Exponentiation

In a retro arcade game you start with 1 rabbit, and every level you clear multiplies your rabbits by factor. The machine is old, so the rabbit counter wraps around like a car odometer: when it would reach wrap, it starts again from 0. The screen therefore shows the true count's remainder after dividing by wrap.

You are building a test tool that jumps straight to any level, even level 1,000,000,000,000, and shows what the counter would read there. Playing through the levels one by one is not an option.

Your task

Write counterAt(factor, levels, wrap). Return factor^levels modulo wrap: the remainder of the true rabbit count after levels levels, divided by wrap.

With 0 levels the count is 1 (even when factor is 0), so return 1 % wrap. The answer is always between 0 and wrap − 1.

counterAt(factor: int, levels: int, wrap: int) → int

Examples

Example 1

Input

factor = 2
levels = 10
wrap = 1000

Output

Why

2 multiplied by itself 10 times is 1,024. A counter that wraps at 1,000 shows 1,024 − 1,000 = 24.

Example 2

Input

factor = 3
levels = 13
wrap = 100

Output

Why

3¹³ = 1,594,323, and the remainder after dividing by 100 is 23. You do not need the full number: knowing that 3⁶ leaves 29 is enough, because 29 × 29 × 3 = 2,523, which also leaves 23.

Example 3

Input

factor = 2
levels = 1000000000000
wrap = 1000000

Output

Why

A trillion levels. Multiplying a trillion times would take far too long, but halving a trillion reaches 0 after about 40 steps, and each step needs at most two multiplications.

Constraints

0 ≤ factor ≤ 1,000,000,000
0 ≤ levels ≤ 1,000,000,000,000,000
1 ≤ wrap ≤ 1,000,000

Start with brute force

Start at 1 and multiply by factor once per level, taking the remainder each time. It is correct, but with up to 10¹⁵ levels that is 10¹⁵ multiplications. At a billion per second it would run for more than 11 days.

Computing the full power first and then taking the remainder is worse: 2^{1,000,000,000,000} has hundreds of billions of digits, and in JavaScript Math.pow loses exact digits long before that (already at 3⁴⁰).

Hints

0 of 4 shown

Hint 1
Suppose you already know what the counter shows after 20 levels. How could you get the reading after 40 levels with a single multiplication?
Hint 2
factor⁴⁰ = factor²⁰ × factor²⁰. Squaring a result doubles the number of levels it covers. Now try an odd number: how do you get factor⁴¹ from factor²⁰?
Hint 3
factor⁴¹ = factor²⁰ × factor²⁰ × factor. So for any levels: get the answer for levels / 2 (rounded down), square it, and if levels is odd multiply by factor once more. Each call halves levels, so the recursion is only about 50 calls deep.
Hint 4
Take the remainder after every multiplication, and reduce factor modulo wrap before using it. Remainders are below 1,000,000, so every product stays under 10¹², which JavaScript numbers hold exactly. Base case: levels = 0 returns 1 % wrap.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

You never need the true count, only its remainder, and you never need to visit every level. Squaring the reading for half the levels gives the reading for all of them, so each call cuts the problem in half.

Trace factor = 3, levels = 13, wrap = 100. The calls go 13 → 6 → 3 → 1 → 0, then the answers come back up:

Level 0: the count is 1.
Level 1 (odd): 1 × 1 = 1, times 3 is 3.
Level 3 (odd): 3 × 3 = 9, times 3 is 27.
Level 6 (even): 27 × 27 = 729, remainder 29.
Level 13 (odd): 29 × 29 = 841, remainder 41. Times 3 is 123, remainder 23.

Seven multiplications instead of thirteen; for a trillion levels it is under a hundred instead of a trillion. Call the function once per level and reuse half. Writing counterAt(…, levels / 2, …) * counterAt(…, levels / 2, …) calls it twice per level, and the number of calls grows back to about levels.

Reference solution

function counterAt(factor, levels, wrap) {
  if (levels === 0) return 1 % wrap; // the count starts at 1
  const half = counterAt(factor, Math.floor(levels / 2), wrap);
  let result = (half * half) % wrap;   // doubles the levels covered
  if (levels % 2 === 1) {
    result = (result * (factor % wrap)) % wrap; // one extra level
  }
  return result;
}

def counter_at(factor, levels, wrap):
    if levels == 0:
        return 1 % wrap  # the count starts at 1
    half = counter_at(factor, levels // 2, wrap)  # count after levels // 2
    result = half * half % wrap                   # doubles the levels covered
    if levels % 2 == 1:
        result = result * (factor % wrap) % wrap  # one extra level
    return result

TimeO(log n)Each call halves levels, so there are about log₂(levels) calls, each doing at most two multiplications.

SpaceO(log n)The recursion is about log₂(levels) calls deep, around 50 for the largest input.

Learn the idea: Divide and Conquer Recursion Math for Algorithms

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code