Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Minimum Steps via Multiply & Mod

HARDProblemSolveExternal Links

Description

You are given two integers start and end, and an array arr of N positive integers.

At each step, you can pick any element from the array, multiply the current value of start by that element, and then take the result modulo 100000. This becomes your new value of start.

Your goal is to transform start into end using the minimum number of such multiply-and-mod operations.

Return the minimum number of steps required. If it is impossible to reach end from start, return -1.

Formally:

  • In one step: start = (start * arr[i]) % 100000 for any valid index i.
  • Find the minimum number of steps to make start == end.

Examples

Example 1

Input: start = 3, end = 30, arr = [2, 5, 7]

Output: 2

Explanation:

  • Step 1: 3 × 2 = 6. After mod 100000 → 6.
  • Step 2: 6 × 5 = 30. After mod 100000 → 30.

We reached the target 30 in 2 steps. There is no way to reach 30 in fewer steps (multiplying 3 by any single element in the array does not produce 30).

Example 2

Input: start = 7, end = 66175, arr = [3, 4, 65]

Output: 4

Explanation:

  • Step 1: 7 × 3 = 21 % 100000 = 21
  • Step 2: 21 × 3 = 63 % 100000 = 63
  • Step 3: 63 × 65 = 4095 % 100000 = 4095
  • Step 4: 4095 × 65 = 266175 % 100000 = 66175

We reached 66175 in 4 steps. Notice how the modulo operation wraps the result back into the range [0, 99999] after the last multiplication.

Example 3

Input: start = 2, end = 3, arr = [4, 6]

Output: -1

Explanation:
Starting from 2, every multiplication produces an even number (2 × 4 = 8, 2 × 6 = 12, 8 × 4 = 32, ...). Since all array elements are even and the start is even, every reachable value remains even. The target 3 is odd, so it can never be reached. Return -1.

Constraints

  • 1 ≤ start, end ≤ 10^5
  • 1 ≤ N ≤ 10^4 (length of the array)
  • 1 ≤ arr[i] ≤ 10^5
  • The modulus value is always 100000
  • start and end are both in the range [0, 99999] after modulo

Editorial

Brute Force - Recursive DFS with Backtracking

Intuition

The most natural way to think about this problem is to try every possible sequence of multiplications and see which one reaches the target in the fewest steps.

Starting from the initial value, at each step we have N choices — multiply by any element in the array. From each resulting value, we again have N choices, and so on. This creates a tree of possibilities where each level represents one step.

We can explore this tree using Depth-First Search (DFS) with backtracking. At each node, we try multiplying by each array element, recurse into the new state, and if we reach the target, we record the depth. We backtrack by removing the state from our visited set so other paths can explore it too.

The fundamental problem with DFS is that it dives deep before exploring wide. It might explore a path of length 10 before discovering there is a path of length 2. It must explore the entire search tree to guarantee finding the minimum.

Step-by-Step Explanation

Let us trace through Example 1: start = 3, end = 30, arr = [2, 5, 7].

Step 1: Begin DFS from value 3, depth 0. Is 3 == 30? No. Try multiplying by each array element.

Step 2: Try 3 × 2 = 6. Recurse into dfs(6, depth=1). Mark 6 as visited.

Step 3: Inside dfs(6), try 6 × 2 = 12. Recurse into dfs(12, depth=2). Mark 12 as visited. DFS is going deeper with the first multiplier.

Step 4: Inside dfs(12), try 12 × 2 = 24. Recurse into dfs(24, depth=3). We are now at depth 3 and still have not found 30. DFS wasted time diving deep before trying other multipliers.

Step 5: 24 does not quickly lead to 30. After exploring several children of 24, backtrack. Unmark 24 from visited.

Step 6: Back at 12, try 12 × 5 = 60. Recurse into dfs(60, depth=3). Still at depth 3, still not at target.

Step 7: 60 does not lead to 30 quickly either. Backtrack from 60 and 12. Return to dfs(6).

Step 8: At dfs(6), now try the second multiplier: 6 × 5 = 30. Recurse into dfs(30, depth=2). Is 30 == 30? YES! Record minimum depth = 2.

Step 9: Backtrack all the way. DFS still needs to explore remaining branches (3×5=15, 3×7=21, etc.) to confirm no shorter path exists. Eventually returns minimum = 2.

DFS found the answer but explored multiple depth-3 branches before finding the depth-2 answer. For larger inputs, this exponential exploration becomes prohibitively slow.

DFS Exploration — Diving Deep Before Finding the Answer — Watch how DFS explores depth-3 branches before discovering the optimal depth-2 path, wasting time on unnecessary deep exploration.

Algorithm

  1. Define a recursive function dfs(current, visited, depth).
  2. Base case: If current == end, update the global minimum with depth and return.
  3. Pruning: If depth >= current_best, stop exploring this branch.
  4. For each element x in the array:
    a. Compute next = (current * x) % 100000.
    b. If next is not in visited:
    • Add next to visited.
    • Recurse: dfs(next, visited, depth + 1).
    • Remove next from visited (backtrack).
  5. Call dfs(start, {start}, 0) and return the recorded minimum (or -1 if no path found).

Code

#include <vector>
#include <unordered_set>
#include <climits>
using namespace std;

class Solution {
public:
    int MOD = 100000;
    int best = INT_MAX;

    void dfs(int current, int target, vector<int>& arr,
             unordered_set<int>& visited, int depth) {
        if (current == target) {
            best = min(best, depth);
            return;
        }
        // Prune: if already deeper than best known answer
        if (depth >= best) return;

        for (int x : arr) {
            int next = (int)((long long)current * x % MOD);
            if (visited.find(next) == visited.end()) {
                visited.insert(next);
                dfs(next, target, arr, visited, depth + 1);
                visited.erase(next); // Backtrack
            }
        }
    }

    int minSteps(int start, int end, vector<int>& arr) {
        if (start == end) return 0;
        unordered_set<int> visited;
        visited.insert(start);
        dfs(start, end, arr, visited, 0);
        return best == INT_MAX ? -1 : best;
    }
};
import sys

class Solution:
    def minSteps(self, start: int, end: int, arr: list[int]) -> int:
        if start == end:
            return 0

        MOD = 100000
        self.best = sys.maxsize

        def dfs(current, visited, depth):
            if current == end:
                self.best = min(self.best, depth)
                return
            if depth >= self.best:
                return  # Prune

            for x in arr:
                nxt = (current * x) % MOD
                if nxt not in visited:
                    visited.add(nxt)
                    dfs(nxt, visited, depth + 1)
                    visited.remove(nxt)  # Backtrack

        visited = {start}
        dfs(start, visited, 0)
        return self.best if self.best != sys.maxsize else -1
import java.util.*;

class Solution {
    int MOD = 100000;
    int best = Integer.MAX_VALUE;

    public int minSteps(int start, int end, int[] arr) {
        if (start == end) return 0;
        Set<Integer> visited = new HashSet<>();
        visited.add(start);
        dfs(start, end, arr, visited, 0);
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    private void dfs(int current, int target, int[] arr,
                     Set<Integer> visited, int depth) {
        if (current == target) {
            best = Math.min(best, depth);
            return;
        }
        if (depth >= best) return; // Prune

        for (int x : arr) {
            int next = (int)((long) current * x % MOD);
            if (!visited.contains(next)) {
                visited.add(next);
                dfs(next, target, arr, visited, depth + 1);
                visited.remove(next); // Backtrack
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(N^D) where D is the depth of the optimal answer

At each level of the recursion tree, we have N choices (one per array element). The tree has depth up to D (the optimal answer). In the worst case, we explore all N^D paths before confirming the minimum. Even with pruning, for large D or large N this becomes exponentially slow. For example, with N=100 and D=10, that is up to 100^10 = 10^20 operations.

Space Complexity: O(D + MOD)

The recursion stack uses O(D) space. The visited set can hold up to MOD (100,000) entries. In practice, space is not the bottleneck — time is.

Why This Approach Is Not Efficient

The DFS approach explores the search tree depth-first, meaning it dives as deep as possible before backtracking. This has two critical problems:

  1. Exponential branching: With N multipliers and an answer depth of D, the tree has up to N^D leaf nodes. Even moderate values like N=10 and D=5 produce 10^5 = 100,000 paths to check.

  2. No shortest-path guarantee per branch: DFS might find a path of length 10 first, then continue exploring to find a shorter one. It cannot stop at the first solution found because that solution might not be optimal.

The fundamental insight is that this problem is equivalent to finding the shortest path in an unweighted graph. Each value from 0 to 99999 is a node, and each multiplication-then-mod operation is an edge. Since all edges have the same weight (1 step), Breadth-First Search (BFS) naturally finds the shortest path by exploring all nodes at distance d before any node at distance d+1.

BFS visits each of the at most 100,000 states exactly once and processes N edges per state, giving O(100,000 × N) time — far better than DFS's exponential worst case.

Comparison chart showing exponential DFS growth versus linear BFS for the multiply-and-mod problem
Comparison chart showing exponential DFS growth versus linear BFS for the multiply-and-mod problem

Optimal Approach - BFS (Breadth-First Search)

Intuition

The key realization is that this problem is a shortest path problem on an implicit graph:

  • Nodes: Every possible value from 0 to 99999 (since all values are taken mod 100000).
  • Edges: From any value v, there is an edge to (v * arr[i]) % 100000 for each element arr[i].
  • Edge weights: All edges have weight 1 (each operation counts as one step).

When all edges have equal weight, BFS finds the shortest path. This is because BFS explores nodes level by level — first all nodes reachable in 1 step, then all nodes reachable in 2 steps, and so on. The first time we reach the target, we are guaranteed it is via the shortest path.

We maintain a distance array dist[] of size 100001 (one entry per possible value). Initially, dist[start] = 0 and all others are -1 (unvisited). We push start into a queue and process it layer by layer. For each value we dequeue, we multiply by every array element, and if the resulting value has not been visited, we record its distance and enqueue it.

The moment we dequeue the target value, we return its distance.

Step-by-Step Explanation

Let us trace through Example 1: start = 3, end = 30, arr = [2, 5, 7].

Step 1: Initialize dist array of size 100001, all set to -1. Set dist[3] = 0. Push 3 into the BFS queue. Queue: [3].

Step 2: Dequeue 3. Is 3 == 30? No. Process all multiplications from value 3.

Step 3: Compute 3 × 2 = 6 (mod 100000 = 6). dist[6] is -1 (unvisited). Set dist[6] = dist[3] + 1 = 1. Enqueue 6. Queue: [6].

Step 4: Compute 3 × 5 = 15. dist[15] is -1. Set dist[15] = 1. Enqueue 15. Queue: [6, 15].

Step 5: Compute 3 × 7 = 21. dist[21] is -1. Set dist[21] = 1. Enqueue 21. Queue: [6, 15, 21]. All level-1 states generated.

Step 6: Dequeue 6. Is 6 == 30? No. Process multiplications from value 6.

Step 7: Compute 6 × 2 = 12. dist[12] is -1. Set dist[12] = dist[6] + 1 = 2. Enqueue 12. Queue: [15, 21, 12].

Step 8: Compute 6 × 5 = 30. dist[30] is -1. Set dist[30] = 2. This is our target! Return 2.

BFS found the answer in just 8 operations by exploring all 1-step states (6, 15, 21) before moving to 2-step states. The first time it encounters 30, it is guaranteed to be via the shortest path.

BFS Level-by-Level — Finding Minimum Steps to 30 — Watch how BFS explores all states at distance 1 before any state at distance 2, guaranteeing the first time we reach the target is the shortest path.

Algorithm

  1. If start == end, return 0 immediately.
  2. Create a distance array dist[] of size 100001, initialized to -1 (unvisited).
  3. Set dist[start % 100000] = 0. Push start into a BFS queue.
  4. While the queue is not empty:
    a. Dequeue the front element top.
    b. If top == end, return dist[top].
    c. For each element x in the array:
    • Compute next = (top * x) % 100000.
    • If dist[next] == -1 (unvisited): set dist[next] = dist[top] + 1 and enqueue next.
  5. If the queue is empty and end was never reached, return -1.

Code

#include <vector>
#include <queue>
#include <cstring>
using namespace std;

class Solution {
public:
    int minSteps(int start, int end, vector<int>& arr) {
        if (start == end) return 0;

        int mod = 100000;
        int dist[100001];
        memset(dist, -1, sizeof(dist));

        queue<int> q;
        q.push(start % mod);
        dist[start % mod] = 0;

        while (!q.empty()) {
            int top = q.front();
            q.pop();

            if (top == end) return dist[top];

            for (int x : arr) {
                int next = (int)((long long)top * x % mod);
                if (dist[next] == -1) {
                    dist[next] = dist[top] + 1;
                    q.push(next);
                }
            }
        }
        return -1;
    }
};
from collections import deque

class Solution:
    def minSteps(self, start: int, end: int, arr: list[int]) -> int:
        if start == end:
            return 0

        mod = 100000
        dist = [-1] * 100001

        q = deque()
        q.append(start % mod)
        dist[start % mod] = 0

        while q:
            top = q.popleft()

            if top == end:
                return dist[top]

            for x in arr:
                nxt = (top * x) % mod
                if dist[nxt] == -1:
                    dist[nxt] = dist[top] + 1
                    q.append(nxt)

        return -1
import java.util.*;

class Solution {
    public int minSteps(int start, int end, int[] arr) {
        if (start == end) return 0;

        int mod = 100000;
        int[] dist = new int[100001];
        Arrays.fill(dist, -1);

        Queue<Integer> q = new LinkedList<>();
        q.add(start % mod);
        dist[start % mod] = 0;

        while (!q.isEmpty()) {
            int top = q.poll();

            if (top == end) return dist[top];

            for (int x : arr) {
                int next = (int)((long) top * x % mod);
                if (dist[next] == -1) {
                    dist[next] = dist[top] + 1;
                    q.add(next);
                }
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(MOD × N) where MOD = 100,000 and N is the array length

Each of the at most 100,000 states (values 0 to 99999) is enqueued and dequeued at most once. For each state, we try all N multipliers. Therefore the total work is at most 100,000 × N operations. With N ≤ 10^4, this gives at most 10^9 operations in the absolute worst case, but in practice BFS terminates as soon as the target is found, processing far fewer states.

Space Complexity: O(MOD)

The distance array dist[] has 100,001 entries. The queue can hold at most 100,000 entries (one per possible state). Both use O(MOD) = O(100,000) = O(10^5) space, which is very manageable.