Minimum Multiplications to Reach End - Graph BFS

Problem and examples

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.

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

How it works

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.

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.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MOD 100000
#define MAX_QUEUE 100000

int minimumMultiplications(int start, int end, int arr[], int arrSize) {
    bool visited[MOD] = {false};
    int queue[MAX_QUEUE];
    int steps[MAX_QUEUE];
    int front = 0, rear = 0;

    queue[rear] = start;
    steps[rear] = 0;
    rear++;
    visited[start] = true;

    while (front < rear) {
        int current = queue[front];
        int step = steps[front];
        front++;

        if (current == end) return step;

        for (int i = 0; i < arrSize; i++) {
            int next = (current * arr[i]) % MOD;
            if (!visited[next]) {
                visited[next] = true;
                queue[rear] = next;
                steps[rear] = step + 1;
                rear++;
            }
        }
    }
    return -1;
}

int main() {
    int arr1[] = {2, 5};
    printf("%d\n", minimumMultiplications(3, 30, arr1, 2));
    int arr2[] = {7};
    printf("%d\n", minimumMultiplications(7, 49, arr2, 1));
    int arr3[] = {2, 3};
    printf("%d\n", minimumMultiplications(10, 1, arr3, 2));
    return 0;
}

C++ implementation

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

const int MOD = 100000;

int minimumMultiplications(int start, int end, vector<int>& arr) {
    vector<bool> visited(MOD, false);
    queue<pair<int, int>> q;

    q.push({start, 0});
    visited[start] = true;

    while (!q.empty()) {
        auto [current, steps] = q.front(); q.pop();
        if (current == end) return steps;

        for (int num : arr) {
            int next = (current * num) % MOD;
            if (!visited[next]) {
                visited[next] = true;
                q.push({next, steps + 1});
            }
        }
    }
    return -1;
}

int main() {
    cout << minimumMultiplications(3, 30, {2, 5}) << endl;
    cout << minimumMultiplications(7, 49, {7}) << endl;
    cout << minimumMultiplications(10, 1, {2, 3}) << endl;
    return 0;
}

Python implementation

from collections import deque

def minimum_multiplications(start, end, arr):
    MOD = 100000
    visited = [False] * MOD
    queue = deque([(start, 0)])
    visited[start] = True

    while queue:
        current, steps = queue.popleft()
        if current == end:
            return steps

        for num in arr:
            next_val = (current * num) % MOD
            if not visited[next_val]:
                visited[next_val] = True
                queue.append((next_val, steps + 1))
    return -1

print(minimum_multiplications(3, 30, [2, 5]))
print(minimum_multiplications(7, 49, [7]))
print(minimum_multiplications(10, 1, [2, 3]))

Java implementation

import java.util.*;

public class MinimumMultiplications {
    static int MOD = 100000;

    public static int minimumMultiplications(int start, int end, int[] arr) {
        boolean[] visited = new boolean[MOD];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start, 0});
        visited[start] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int value = curr[0], steps = curr[1];

            if (value == end) return steps;

            for (int num : arr) {
                int next = (value * num) % MOD;
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(new int[]{next, steps + 1});
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(minimumMultiplications(3, 30, new int[]{2, 5}));
        System.out.println(minimumMultiplications(7, 49, new int[]{7}));
        System.out.println(minimumMultiplications(10, 1, new int[]{2, 3}));
    }
}

JavaScript implementation

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]));
console.log(minimumMultiplications(7, 49, [7]));
console.log(minimumMultiplications(10, 1, [2, 3]));

Go implementation

package main

import (
  "fmt"
)

const MOD = 100000

func minimumMultiplications(start, end int, arr []int) int {
  visited := make([]bool, MOD)
  type state struct{ val, steps int }
  queue := []state{{start, 0}}
  visited[start] = true

  for len(queue) > 0 {
    curr := queue[0]
    queue = queue[1:]

    if curr.val == end {
      return curr.steps
    }

    for _, num := range arr {
      next := (curr.val * num) % MOD
      if !visited[next] {
        visited[next] = true
        queue = append(queue, state{next, curr.steps + 1})
      }
    }
  }
  return -1
}

func main() {
  fmt.Println(minimumMultiplications(3, 30, []int{2, 5}))
  fmt.Println(minimumMultiplications(7, 49, []int{7}))
  fmt.Println(minimumMultiplications(10, 1, []int{2, 3}))
}

Rust implementation

use std::collections::VecDeque;

fn minimum_multiplications(start: usize, end: usize, arr: &[usize]) -> i32 {
    const MOD: usize = 100000;
    let mut visited = vec![false; MOD];
    let mut queue = VecDeque::from([(start, 0)]);
    visited[start] = true;

    while let Some((current, steps)) = queue.pop_front() {
        if current == end {
            return steps;
        }
        for &num in arr {
            let next = (current * num) % MOD;
            if !visited[next] {
                visited[next] = true;
                queue.push_back((next, steps + 1));
            }
        }
    }
    -1
}

fn main() {
    println!("{}", minimum_multiplications(3, 30, &[2, 5]));
    println!("{}", minimum_multiplications(7, 49, &[7]));
    println!("{}", minimum_multiplications(10, 1, &[2, 3]));
}

Kotlin implementation

import java.util.*

fun minimumMultiplications(start: Int, end: Int, arr: IntArray): Int {
    val MOD = 100000
    val visited = BooleanArray(MOD)
    val queue: Queue<Pair<Int, Int>> = LinkedList()
    queue.add(Pair(start, 0))
    visited[start] = true

    while (queue.isNotEmpty()) {
        val (current, steps) = queue.poll()
        if (current == end) return steps

        for (num in arr) {
            val next = (current * num) % MOD
            if (!visited[next]) {
                visited[next] = true
                queue.add(Pair(next, steps + 1))
            }
        }
    }
    return -1
}

fun main() {
    println(minimumMultiplications(3, 30, intArrayOf(2, 5)))
    println(minimumMultiplications(7, 49, intArrayOf(7)))
    println(minimumMultiplications(10, 1, intArrayOf(2, 3)))
}

Swift implementation

import Foundation

func minimumMultiplications(start: Int, end: Int, arr: [Int]) -> Int {
    let MOD = 100000
    var visited = [Bool](repeating: false, count: MOD)
    var queue: [(Int, Int)] = [(start, 0)]
    visited[start] = true

    while !queue.isEmpty {
        let (current, steps) = queue.removeFirst()
        if current == end {
            return steps
        }
        for num in arr {
            let next = (current * num) % MOD
            if !visited[next] {
                visited[next] = true
                queue.append((next, steps + 1))
            }
        }
    }
    return -1
}

print(minimumMultiplications(start: 3, end: 30, arr: [2, 5]))
print(minimumMultiplications(start: 7, end: 49, arr: [7]))
print(minimumMultiplications(start: 10, end: 1, arr: [2, 3]))

TypeScript implementation

function minimumMultiplications(start: number, end: number, arr: number[]): number {
  const MOD = 100000;
  const visited = new Array(MOD).fill(false);
  const queue: [number, number][] = [[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]));
console.log(minimumMultiplications(7, 49, [7]));
console.log(minimumMultiplications(10, 1, [2, 3]));