Minimum Multiplications to Reach End Using Graph BFS

Problem Statement❯

You're given a starting number start, a target number end, and an array of integers arr. In each step, you can multiply start by any number in arr and take the result modulo 100000 (i.e., (start * x) % 100000).

Your goal is to reach end from start using the minimum number of such operations. If it's not possible to reach the end number, return -1.

Examples❯

Start	End	Array	Output	Description
3	30	[2, 5]	2	3 * 2 = 6, then 6 * 5 = 30
7	49	[7]	1	7 * 7 = 49
10	1	[2, 3]	-1	Cannot reach 1 from 10 with the given array
1	100000	[99999]	1	1 * 99999 % 100000 = 99999
2	2	[1]	0	Start equals end, no operation needed

Solution❯

Understanding the Problem

We are given a start number and an end number. Also, we are provided with an array arr[] of multipliers. In each move, we can multiply the current number with any number from arr[], and then take the result modulo 100000.

The goal is to find the minimum number of such multiplications required to reach the end number starting from start. If it's not possible to reach end, we should return -1.

This is a classic shortest path problem in disguise, where each number from 0 to 99999 can be thought of as a node in a graph, and we can move from one node to another by performing a multiplication and taking modulo 100000.

Step-by-Step Solution with Example

Step 1: Visualize as a Graph

We treat every number from 0 to 99999 as a node. From a node u, we can go to another node v if v = (u * x) % 100000 where x is any element from arr[].

This gives us a huge graph with up to 100000 nodes, but we only need to explore reachable nodes starting from start.

Step 2: Use BFS to Find Minimum Steps

Since all transitions are uniform (1 step each), we can apply Breadth-First Search (BFS), which always finds the shortest path in an unweighted graph.

Step 3: Track Visited Nodes

We keep an array dist[100000] to track the number of steps it takes to reach each node. Initialize all entries to -1 except dist[start] which is 0.

Step 4: Process Queue and Apply Multiplications

While processing the BFS queue, for each number curr, we try all multipliers x from arr. We calculate next = (curr * x) % 100000. If dist[next] is -1, it means we haven't reached it yet, so we set dist[next] = dist[curr] + 1 and add next to the queue.

Step 5: Stop When Target is Reached

If at any point curr becomes equal to end, we return dist[curr] as the answer. If the queue becomes empty and we haven’t reached end, we return -1.

Example:

Suppose start = 3, end = 30, and arr = [2, 5].

From 3, multiply by 2 → 6
From 3, multiply by 5 → 15
From 15, multiply by 2 → 30

We reached 30 in 2 steps: 3 → 15 → 30. So, the answer is 2.

Edge Cases

Start is equal to End: If start == end, we return 0 immediately because no steps are needed.
Multiplier array has 0: Since multiplying by 0 always leads to 0, it can trap the process. It should be handled carefully.
Unreachable Target: If the end number is not reachable using the given multipliers and modulo arithmetic, BFS will finish without reaching end, and we return -1.
Duplicates in arr[]: No problem — duplicates don’t affect the correctness but may cause redundant attempts, so we can use a set if needed.

Finally

This problem beautifully shows how arithmetic operations can be transformed into a graph traversal problem. By understanding that each multiplication step creates a connection between nodes, and using BFS to ensure minimum steps, we solve it efficiently even with a large search space. Always begin by modeling the problem intuitively and thinking about how to simulate the allowed operations as graph edges.

Algorithm Steps❯

Initialize a queue with a pair (start, 0) representing the starting number and 0 steps taken.
Use a visited array of size 100000 to mark visited nodes.
While the queue is not empty:

Dequeue the current node and steps.
If the node equals end, return the steps.
For each number x in arr:

Compute next = (current * x) % 100000.
If next is not visited, mark it and enqueue (next, steps + 1).

If the loop ends without finding end, return -1.

Code

JavaScript

function minimumMultiplications(start, end, arr) {
  const MOD = 100000;
  const visited = new Array(MOD).fill(false);
  const queue = [[start, 0]];

  visited[start] = true;

  while (queue.length > 0) {
    const [current, steps] = queue.shift();
    if (current === end) return steps;

    for (const num of arr) {
      const next = (current * num) % MOD;
      if (!visited[next]) {
        visited[next] = true;
        queue.push([next, steps + 1]);
      }
    }
  }

  return -1;
}

console.log(minimumMultiplications(3, 30, [2, 5])); // Output: 2
console.log(minimumMultiplications(7, 49, [7]));    // Output: 1
console.log(minimumMultiplications(10, 1, [2, 3])); // Output: -1

⬅ Previous TopicNumber of Ways to Reach Destination in Shortest Time - Graph Problem

Next Topic ⮕Bellman-Ford Algorithm for Shortest Paths

Comments

Loading comments...