Minimum Multiplications to Reach End
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Minimum Steps to Reach a Target Number via Multiplications and Modulo Operation, Graph, Breadth-First Search, Dijkstra's Algorithm, Queue, Modular Arithmetic, Time Complexity, Space Complexity, Arrays, graph representation, mathematical operations, visited tracking, queue, shortest path algorithms, bfs.
Minimum Multiplications to reach End Problem Statement Given three integers start, end, and an array arr of N numbers. At each step, the start number is multiplied by any number in the arr and then a modulo operation with 100000 is performed to get the new start number. Your task is to find the minimum number of steps (multiplications) required to transform the initial start number into the end number. If it is not possible to reach the end number, return 1. Input Specification An integer array arr of size N. An integer start, representing the initial number. An integer end, representing the target number. Output Specification Return an integer representing the minimum number of steps to reach end from start. Return 1 if end is unreachable. Constraints All intermediate calculations are performed modulo 100000. Sample Test Cases Sample 1 Input: Output: Explanation: Step 1: 3 2 = 6 % 100000 = 6 Step 2: 6 5 = 30 % 100000 = 30 Therefore, in a minimum of 2 multiplications, the end number (30) is reached. Sample 2 Input: Output: 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 Therefore, in a minimum of 4 multiplications, the end number (66175) is reached.