Dado inicio, final y una array de N números. En cada paso, el inicio se multiplica con cualquier número en la array y luego se realiza la operación de modificación con 100000 para obtener el nuevo inicio. La tarea es encontrar los pasos mínimos en los que se puede lograr el fin comenzando desde el principio.
Ejemplos:
Entrada: inicio = 3 fin = 30 a[] = {2, 5, 7}
Salida: 2
Paso 1: 3*2 = 6 % 100000 = 6
Paso 2: 6*5 = 30 % 100000 = 30
Entrada: inicio = 7 fin = 66175 a[] = {3, 4, 65}
Salida: 4
Paso 1: 7*3 = 21 % 100000 = 21
Paso 2: 21*3 = 6 % 100000 = 63
Paso 3: 63*65 = 4095 % 100000 = 4095
Paso 4: 4095*65 = 266175 % 100000 = 66175
Enfoque: Dado que en el problema anterior el módulo dado es 100000, el número máximo de estados será 10 5 . Todos los estados se pueden verificar usando BFS simple. Inicialice una array ans[] con -1 que marca que el estado no ha sido visitado. ans[i] almacena el número de pasos dados para llegar a i desde el inicio. Inicialmente empuje el inicio a la cola, luego aplique BFS. Haga estallar el elemento superior y verifique si es igual al final, si es así, imprima el ans[end]. Si el elemento no es igual al elemento superior, multiplique el elemento superior con cada elemento de la array y realice una operación de modificación. Si el estado del elemento multiplicado no ha sido visitado previamente, entonces insértelo en la cola. Inicialice ans[pushed_element] por ans[top_element] + 1. Una vez que se visitan todos los estados, y no se puede alcanzar el estado realizando todas las multiplicaciones posibles, imprima -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum steps
// to reach end from start by performing
// multiplications and mod operations with array elements
#include <bits/stdc++.h>
using namespace std;
// Function that returns the minimum operations
int minimumMulitplications(int start, int end, int a[], int n)
{
// array which stores the minimum steps
// to reach i from start
int ans[100001];
// -1 indicated the state has not been visited
memset(ans, -1, sizeof(ans));
int mod = 100000;
// queue to store all possible states
queue<int> q;
// initially push the start
q.push(start % mod);
// to reach start we require 0 steps
ans[start] = 0;
// till all states are visited
while (!q.empty()) {
// get the topmost element in the queue
int top = q.front();
// pop the topmost element
q.pop();
// if the topmost element is end
if (top == end)
return ans[end];
// perform multiplication with all array elements
for (int i = 0; i < n; i++) {
int pushed = top * a[i];
pushed = pushed % mod;
// if not visited, then push it to queue
if (ans[pushed] == -1) {
ans[pushed] = ans[top] + 1;
q.push(pushed);
}
}
}
return -1;
}
// Driver Code
int main()
{
int start = 7, end = 66175;
int a[] = { 3, 4, 65 };
int n = sizeof(a) / sizeof(a[0]);
// Calling function
cout << minimumMulitplications(start, end, a, n);
return 0;
}
Java
// Java program to find the minimum steps
// to reach end from start by performing
// multiplications and mod operations with array elements
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class GFG {
// Function that returns the minimum operations
static int minimumMulitplications(int start, int end, int a[], int n) {
// array which stores the minimum steps
// to reach i from start
int ans[] = new int[100001];
// -1 indicated the state has not been visited
Arrays.fill(ans, -1);
int mod = 100000;
// queue to store all possible states
Queue<Integer> q = new LinkedList<>();
// initially push the start
q.add(start % mod);
// to reach start we require 0 steps
ans[start] = 0;
// till all states are visited
while (!q.isEmpty()) {
// get the topmost element in the queue
int top = q.peek();
// pop the topmost element
q.remove();
// if the topmost element is end
if (top == end) {
return ans[end];
}
// perform multiplication with all array elements
for (int i = 0; i < n; i++) {
int pushed = top * a[i];
pushed = pushed % mod;
// if not visited, then push it to queue
if (ans[pushed] == -1) {
ans[pushed] = ans[top] + 1;
q.add(pushed);
}
}
}
return -1;
}
// Driver Code
public static void main(String args[]) {
int start = 7, end = 66175;
int a[] = {3, 4, 65};
int n = a.length;
// Calling function
System.out.println(minimumMulitplications(start, end, a, n));
}
}
// This code is contributed by PrinciRaj19992
Python3
# Python3 program to find the minimum steps # to reach end from start by performing # multiplications and mod operations with # array elements from collections import deque # Function that returns the minimum operations def minimumMulitplications(start, end, a, n): # array which stores the minimum # steps to reach i from start ans = [-1 for i in range(100001)] # -1 indicated the state has # not been visited mod = 100000 q = deque() # queue to store all possible states # initially push the start q.append(start % mod) # to reach start we require 0 steps ans[start] = 0 # till all states are visited while (len(q) > 0): # get the topmost element in the # queue, pop the topmost element top = q.popleft() # if the topmost element is end if (top == end): return ans[end] # perform multiplication with # all array elements for i in range(n): pushed = top * a[i] pushed = pushed % mod # if not visited, then push it to queue if (ans[pushed] == -1): ans[pushed] = ans[top] + 1 q.append(pushed) return -1 # Driver Code start = 7 end = 66175 a = [3, 4, 65] n = len(a) # Calling function print(minimumMulitplications(start, end, a, n)) # This code is contributed by mohit kumar
C#
// C# program to find the minimum steps
// to reach end from start by performing
// multiplications and mod operations with array elements
using System;
using System.Collections.Generic;
class GFG
{
// Function that returns the minimum operations
static int minimumMulitplications(int start, int end,
int []a, int n)
{
// array which stores the minimum steps
// to reach i from start
int []ans = new int[100001];
// -1 indicated the state has not been visited
for(int i = 0; i < ans.Length; i++)
ans[i] = -1;
int mod = 100000;
// queue to store all possible states
Queue<int> q = new Queue<int>();
// initially push the start
q.Enqueue(start % mod);
// to reach start we require 0 steps
ans[start] = 0;
// till all states are visited
while (q.Count != 0)
{
// get the topmost element in the queue
int top = q.Peek();
// pop the topmost element
q.Dequeue();
// if the topmost element is end
if (top == end)
{
return ans[end];
}
// perform multiplication with all array elements
for (int i = 0; i < n; i++)
{
int pushed = top * a[i];
pushed = pushed % mod;
// if not visited, then push it to queue
if (ans[pushed] == -1)
{
ans[pushed] = ans[top] + 1;
q.Enqueue(pushed);
}
}
}
return -1;
}
// Driver Code
public static void Main(String []args)
{
int start = 7, end = 66175;
int []a = {3, 4, 65};
int n = a.Length;
// Calling function
Console.WriteLine(minimumMulitplications(start, end, a, n));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to find the minimum steps
// to reach end from start by performing
// multiplications and mod operations with array elements
// Function that returns the minimum operations
function minimumMulitplications(start,end,a,n)
{
// array which stores the minimum steps
// to reach i from start
let ans = new Array(100001);
// -1 indicated the state has not been visited
for(let i=0;i<ans.length;i++)
{
ans[i]=-1;
}
let mod = 100000;
// queue to store all possible states
let q = [];
// initially push the start
q.push(start % mod);
// to reach start we require 0 steps
ans[start] = 0;
// till all states are visited
while (q.length!=0) {
// get the topmost element in the queue
let top = q[0];
// pop the topmost element
q.shift();
// if the topmost element is end
if (top == end) {
return ans[end];
}
// perform multiplication with all array elements
for (let i = 0; i < n; i++) {
let pushed = top * a[i];
pushed = pushed % mod;
// if not visited, then push it to queue
if (ans[pushed] == -1) {
ans[pushed] = ans[top] + 1;
q.push(pushed);
}
}
}
return -1;
}
// Driver Code
let start = 7, end = 66175;
let a=[3, 4, 65];
let n = a.length;
// Calling function
document.write(minimumMulitplications(start, end, a, n));
// This code is contributed by unknown2108
</script>
4
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)