Dada una array de enteros y un número K con valores inicial y final. Su tarea es encontrar la cantidad mínima de pasos necesarios para obtener el valor final a partir del valor inicial utilizando los elementos de la array. Solo puede agregar (operación de agregar% 1000) en valores para obtener el valor final. En cada paso, puede agregar cualquiera de los elementos de la array con la operación de módulo.
Ejemplos:
Entrada: inicial = 1, final = 6, a[] = {1, 2, 3, 4}
Salida: 2
Paso 1: (1 + 1 ) % 1000 = 2.
Paso 2: (2 + 4) % 1000 = 6 (que es el valor final requerido).Entrada: inicio = 998 fin = 2 a[] = {2, 1, 3}
Salida: 2
Paso 1: (998 + 2) % 1000 = 0.
Paso 2: (0 + 2) % 1000 = 2.
O
Paso 1: (998 + 1) % 1000 = 999.
Paso 2: (999 + 3) % 1000 = 2
Enfoque: Dado que en el problema anterior el módulo dado es 1000, el número máximo de estados será 10 3 . 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, agregue el elemento superior con todos los elementos de la array y realice una operación de modificación con 1000. Si el estado del elemento agregado no se ha visitado anteriormente, 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 // additions and mod operations with array elements #include <bits/stdc++.h> using namespace std; // Function that returns the minimum operations int minimumAdditions(int start, int end, int a[], int n) { // array which stores the minimum steps // to reach i from start int ans[1001]; // -1 indicated the state has not been visited memset(ans, -1, sizeof(ans)); int mod = 1000; // 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 addition 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 = 998, end = 2; int a[] = { 2, 1, 3 }; int n = sizeof(a) / sizeof(a[0]); // Calling function cout << minimumAdditions(start, end, a, n); return 0; }
Java
// Java program to find the minimum steps // to reach end from start by performing // additions and mod operations with array elements import java.util.*; class GFG { // Function that returns // the minimum operations static int minimumAdditions(int start, int end, int a[], int n) { // array which stores the minimum steps // to reach i from start int ans[] = new int[1001]; // -1 indicated the state has not been visited Arrays.fill(ans, -1); int mod = 1000; // queue to store all possible states Queue<Integer> q = new java.util.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.poll(); // if the topmost element is end if (top == end) { return ans[end]; } // perform addition 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 = 998, end = 2; int a[] = {2, 1, 3}; int n = a.length; // Calling function System.out.println(minimumAdditions(start, end, a, n)); } } /* This code contributed by PrinciRaj1992 */
Python3
# Python3 program to find the minimum steps # to reach end from start by performing # additions and mod operations with array # elements from collections import deque from typing import List # Function that returns the minimum operations def minimumAdditions(start: int, end: int, a: List[int], n: int) -> int: # Array which stores the minimum steps # to reach i from start # -1 indicated the state has not been visited ans = [-1] * 1001 mod = 1000 # Queue to store all possible states q = deque() # Initially push the start q.append(start % mod) # To reach start we require 0 steps ans[start] = 0 # Till all states are visited while q: # Get the topmost element in the queue top = q[0] # Pop the topmost element q.popleft() # If the topmost element is end if (top == end): return ans[end] # Perform addition 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 if __name__ == "__main__": start = 998 end = 2 a = [ 2, 1, 3 ] n = len(a) # Calling function print(minimumAdditions(start, end, a, n)) # This code is contributed by sanjeev2552
C#
// C# program to find the minimum steps // to reach end from start by performing // additions and mod operations with array elements using System; using System.Collections.Generic; class GFG { // Function that returns // the minimum operations static int minimumAdditions(int start, int end, int []a, int n) { // array which stores the minimum steps // to reach i from start int []ans = new int[1001]; // -1 indicated the state has not been visited for(int i = 0; i < 1001; i++) { ans[i] = -1; } int mod = 1000; // 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 addition 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 = 998, end = 2; int []a = {2, 1, 3}; int n = a.Length; // Calling function Console.WriteLine(minimumAdditions(start, end, a, n)); } } // This code has been contributed by 29AjayKumar
Javascript
<script> // Javascript program to find the minimum steps // to reach end from start by performing // additions and mod operations with array elements // Function that returns // the minimum operations function minimumAdditions(start,end,a,n) { // array which stores the minimum steps // to reach i from start let ans = new Array(1001); // -1 indicated the state has not been visited for(let i=0;i<1001;i++) ans[i]=-1; let mod = 1000; // 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 addition 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 = 998, end = 2; let a=[2, 1, 3]; let n = a.length; // Calling function document.write(minimumAdditions(start, end, a, n)); // This code is contributed by rag2127 </script>
2
Complejidad de tiempo : O(N)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA