Shortest Path From 1 To n

Problem Overview

Starting at 1, each move either adds 1 or multiplies by 3.

Intuition

Starting at 1, each move either adds 1 or multiplies by 3. Filling a DP table up to n works but is linear in n. The same distances appear by walking backward from n: subtract 1, or divide by 3 whenever n is a multiple of 3. Taking the divide whenever it is available is optimal, because each forward multiply covers a long stretch that would otherwise need many additions.

Algorithm

1Start steps at 0.
2While n is greater than 1, if n is divisible by 3 replace it with n / 3, otherwise replace it with n - 1.
3Increase steps by one after each change.
4When n reaches 1, return steps.

Example Walkthrough

Input: n = 10

1. 10 is not a multiple of 3, so subtract to 9.
2. 9 divides by 3 to give 3, then 3 divides by 3 to give 1.
3. Three backward moves match the forward path 1 to 3 to 9 to 10.

Output: 3

Common Pitfalls

• n = 1 needs zero steps. Return 0 without entering the loop.
• Do not multiply by 2; the only jump move is multiply by 3.
• A full DP array is correct but uses linear time and memory that the backward walk avoids.
• Always divide when divisible by 3. Skipping a divide to subtract first never shortens the path.

Shortest Path From 1 To n.java

Java

// Approach: From 1 you may add 1 or multiply by 3. Working backward from n,
// those moves are subtract 1 or divide by 3 when n is a multiple of 3. Dividing
// whenever possible is optimal, because a multiply jumps over a whole range of
// add-1 steps. Count the operations until 1 remains.
// Complexity: O(log n) time, O(1) space.
class Solution {
    public int minimumStep(int n) {
        int steps = 0;
        while (n > 1) {
            if (n % 3 == 0)
                n /= 3;
            else
                n--;
            steps++;
        }
        return steps;
    }
}

Was this solution helpful?