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.

Algorithm Steps

1. Initialize a queue with a pair (start, 0) representing the starting number and 0 steps taken.
2. Use a visited array of size 100000 to mark visited nodes.
3. While the queue is not empty:
1. Dequeue the current node and steps.
2. If the node equals end, return the steps.
3. For each number x in arr:
1. Compute next = (current * x) % 100000.
2. If next is not visited, mark it and enqueue (next, steps + 1).
4. If the loop ends without finding end, return -1.

Code

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