Given an array arr containing N positive multipliers, a starting value start, and a target value end, one operation selects any multiplier and replaces the current value with (current×multiplier)%100000.
Return the minimum number of operations required to reach end from start. Return -1 when no multiplication sequence reaches the target.
Constraints 0 ≤ start < 100000, 0 ≤ end < 100000
Both start and end are valid modulo-100000 residues, allowing direct indexing in the distance array.
Example 1
Input: arr = [2,5,7], start = 3, end = 30
Output: 2
Explanation: Multiplication by 2 changes 3 into 6, and multiplication by 5 changes 6 into 30.
Example 2
Input: arr = [3,4,65], start = 7, end = 66175
Output: 4
Explanation: A shortest sequence is 7->21->63->4095->66175, using multipliers 3,3,65,65.
Approach
Modulo 100000 restricts every generated value to M=100000 possible residues. Every residue represents a graph node, while multiplication by an allowed value creates a directed edge to (current×multiplier)%M.
Every edge represents one operation, so Breadth First Search explores residues in increasing operation count. A distance array marks each residue during first discovery, preventing repeated processing and preserving the shortest distance.
Algorithm
Return
0whenstartequalsend, since no multiplication is required.Initialize a distance array of size
M=100000with-1, where-1represents an unvisited residue.Set
distance[start]=0and addstartto a queue, establishing the initial BFS state.Continue BFS while the queue contains residues and remove the front residue.
For every multiplier, calculate
next=(current×multiplier)%Musing a sufficiently wide integer type.For every unvisited
next, assigndistance[current]+1; return immediately upon reachingend, or addnextto the queue.Return
-1when the queue becomes empty without discovering the target residue.
Dry Run
minimum multiplication 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return the minimum multiplication count from start to end. int minimumMultiplications( vector<int>& arr, int start, int end ) { const int MOD = 100000; // Input constraints guarantee valid residue indices. // 0 <= start, end < MOD // Handle the zero-operation case before BFS. if (start == end) { return 0; } // Store the shortest distance to every modular state. vector<int> distance(MOD, -1); queue<int> pending; // Mark and enqueue the initial residue. distance[start] = 0; pending.push(start); // Explore residues in increasing operation count. while (!pending.empty()) { int current = pending.front(); pending.pop(); // Generate every residue reachable in one operation. for (int multiplier : arr) { int next = static_cast<int>( (1LL * current * multiplier) % MOD ); // Skip previously discovered residues. if (distance[next] != -1) { continue; } // Record the first and shortest distance. distance[next] = distance[current] + 1; // Return after the first target discovery. if (next == end) { return distance[next]; } // Continue BFS from the new residue. pending.push(next); } } // Report an unreachable target. return -1; }};// Driver code.int main() { vector<int> arr = {2, 5, 7}; int start = 3; int end = 30; Solution solution; cout << solution.minimumMultiplications(arr, start, end); return 0;}Complexity Analysis
Time Complexity: O(N×M), where N is the number of multipliers and M=100000 is the number of modular states; every state tries all multipliers once.
Space Complexity: O(M), where the distance array and BFS queue can each store up to M=100000 residues.
Interview follow-up Questions
Every graph edge has unit cost, and BFS visits residues in increasing edge count.
Be the first to add a comment.