Problem

Given a positive integer N, find the smallest number of steps it will take to reach 1.

There are two kinds of permitted steps:

  • You may decrement N to N - 1.
  • If a * b = N, you may decrement N to the larger of a and b.

Examples

Example 1:

1
2
3

Input: N = 100
Output: 5
Explanation: 100 -> 1 with the following route: `100 -> 10 -> 9 -> 3 -> 2 -> 1`.

Solution

Method 1 - BFS

The problem is essentially finding the shortest path from ( N ) to 1 using the provided operations. This can be efficiently tackled using a breadth-first search (BFS) algorithm. BFS is suitable for this problem because it explores all possible moves at each level before moving to the next, ensuring that the shortest path is found.

Here’s how we can approach it:

  1. Operations:
    • Decrement ( N ) to ( N - 1 ).
    • If ( a . b = N ), decrement ( N ) to the larger of ( a ) and ( b ).
  2. Breadth-First Search (BFS):
    • Use a queue to explore all possible steps, starting from ( N ).
    • Track visited numbers to avoid redundant calculations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

public class MinStepsToOne {

	public static int minStepsToOne(int n) {
		// Base case
		if (n == 1) {
			return 0;
		}

		// Queue for BFS
		Queue < int[] > queue = new LinkedList<>();
		queue.offer(new int[] {
			n, 0
		}); // {current number, current steps}
		Set<Integer> visited = new HashSet<>();

		while (!queue.isEmpty()) {
			int[] currentPair = queue.poll();
			int current = currentPair[0];
			int steps = currentPair[1];

			// If current number reaches 1, return the steps
			if (current == 1) {
				return steps;
			}

			// Add the decrement operation
			if (!visited.contains(current - 1)) {
				visited.add(current - 1);
				queue.offer(new int[] {
					current - 1, steps + 1
				});
			}

			// Add the factor reduction operation
			for (int i = 1; i <= Math.sqrt(current); i++) {
				if (current % i == 0) {
					int largerFactor = Math.max(i, current / i);

					if (!visited.contains(largerFactor)) {
						visited.add(largerFactor);
						queue.offer(new int[] {
							largerFactor, steps + 1
						});
					}
				}
			}
		}

		// If we exhaust the queue without finding 1, return -1 (error case)
		return -1;
	}

	public static void main(String[] args) {
		int n = 100;
		System.out.println("Minimum number of steps to reach 1 from " + n + " is " + minStepsToOne(n));
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def min_steps_to_one(n):
    # Base case
    if n == 1:
        return 0

    # Queue for BFS
    queue = deque([(n, 0)])  # (current number, current steps)
    visited = set()  # To keep track of visited numbers

    while queue:
        current, steps = queue.popleft()

        # If current number reaches 1, return the steps
        if current == 1:
            return steps

        # Add the decrement operation
        if current - 1 not in visited:
            visited.add(current - 1)
            queue.append((current - 1, steps + 1))

        # Add the factor reduction operation
        for i in range(1, int(current**0.5) + 1):
            if current % i == 0:
                larger_factor = max(i, current // i)
                if larger_factor not in visited:
                    visited.add(larger_factor)
                    queue.append((larger_factor, steps + 1))

Complexity

  • ⏰ Time complexity: O(n * √n) where n is number
    • Decrement Operation: Each number ( n ) can be decremented to ( n-1 ), which is an ( O(1) ) operation.
    • Factor Operations: For each number ( n ), we find its factors up to ( \sqrt{n} ):
      • Iterating through the factors takes ( O(\sqrt{n}) ) time.
      • Each factor pair is checked whether it has been visited.
  • 🧺 Space complexity: O(n)