Número mínimo de operaciones de suma y módulo usando números dados para alcanzar el objetivo

Dado un número N , una array arr[] y un número objetivo K , la tarea es encontrar el número mínimo de movimientos para alcanzar K eligiendo cualquier elemento de la array y cambiando N a (N + arr[i]) mod 100000 en cada Muevete.

Ejemplos:

Entrada: N = 99880, K = 89, arr = {100, 3}
Salida: 5
Explicación: El número «100» se usa 2 veces y el número «3» se presiona 3 veces, lo que da como resultado K de N

Entrada: N = 10000, K = 10004, arr = {1}
Salida: 4

Enfoque: el problema anterior se puede resolver utilizando la programación dinámica porque tiene subproblemas superpuestos y una subestructura óptima.  Inicialice la tabla dp donde dp[i] almacena los movimientos mínimos necesarios para alcanzar el estado i en N y dp[target] será la respuesta requerida. De cada arr[i], encuentre todos los estados alcanzables y minimice el valor de dp . Siga los pasos a continuación para el enfoque:

• Inicialice una array , por ejemplo, dp[ ] para almacenar los movimientos mínimos necesarios para alcanzar el estado i.
• Itere sobre la array arr y verifique cada posición del número actual N como x :
  • si dp[x] es igual a -1, entonces continúa.
  • de lo contrario, itere un ciclo while hasta que dp[next] sea igual a -1 o dp[next] sea mayor que dp[x] + 1 y actualice next como (x+buttons[i])%100000 y dp[next] como dp[ x]+ 1 .
• Finalmente, devuelve el valor de dp[objetivo].

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum moves
// to reach K from N
int minPushes(int N, int K, vector<int> arr)
{
 
    // Initialization of dp vector
    vector<int> dp(100000, -1);
 
    // dp[i] = minimum pushes
    // required to reach i
    dp[N] = 0;
 
    // Traversing through the buttons
    for (int i = 0; i < arr.size(); i++) {
 
        // Iterating through all the positions
        for (int xx = 0; xx < 100000; xx++) {
            int x = xx;
 
            // If not visited
            if (dp[x] == -1)
                continue;
 
            // Next status of lock
            int next = (x + arr[i]) % 100000;
            while (dp[next] == -1
                   || dp[next] > dp[x] + 1) {
                dp[next] = dp[x] + 1;
 
                // Advance to next state
                x = next;
                next = (next + arr[i]) % 100000;
            }
        }
    }
 
    // Return the final dp[target]
    return dp[K];
}
 
// Driver function
int main()
{
    // Given Input
    int N = 99880, K = 89;
    vector<int> arr{ 100, 3 };
 
    // Function Call
    cout << minPushes(N, K, arr);
 
    return 0;
}

// Java implementation of the above approach
class GFG{
 
// Function to find the minimum moves
// to reach K from N
static int minPushes(int N, int K, int[] arr)
{
 
    // Initialization of dp vector
    int[] dp = new int[100000];
    for (int i = 0; i < dp.length; i++)
        dp[i] = -1;
   
    // dp[i] = minimum pushes
    // required to reach i
    dp[N] = 0;
 
    // Traversing through the buttons
    for (int i = 0; i < arr.length; i++) {
 
        // Iterating through all the positions
        for (int xx = 0; xx < 100000; xx++) {
            int x = xx;
 
            // If not visited
            if (dp[x] == -1)
                continue;
 
            // Next status of lock
            int next = (x + arr[i]) % 100000;
            while (dp[next] == -1
                   || dp[next] > dp[x] + 1) {
                dp[next] = dp[x] + 1;
 
                // Advance to next state
                x = next;
                next = (next + arr[i]) % 100000;
            }
        }
    }
 
    // Return the final dp[target]
    return dp[K];
}
 
// Driver function
public static void main(String[] args)
{
    // Given Input
    int N = 99880, K = 89;
    int[] arr = { 100, 3 };
 
    // Function Call
    System.out.print(minPushes(N, K, arr));
 
}
}
 
// This code is contributed by shikhasingrajput

# Python program for the above approach
 
# Function to find the minimum moves
# to reach K from N
def minPushes(N, K, arr):
 
    # Initialization of dp vector
    dp = [-1] * 100000
 
    # dp[i] = minimum pushes
    # required to reach i
    dp[N] = 0
 
    # Traversing through the buttons
    for i in range(len(arr)):
 
        # Iterating through all the positions
        for xx in range(100000):
            x = xx
 
            # If not visited
            if (dp[x] == -1) :
                continue
 
            # Next status of lock
            next = (x + arr[i]) % 100000
            while (dp[next] == -1
                   or dp[next] > dp[x] + 1) :
                dp[next] = dp[x] + 1
 
                # Advance to next state
                x = next
                next = (next + arr[i]) % 100000
             
    # Return the final dp[target]
    return dp[K]
 
# Driver function
 
# Given Input
N = 99880
K = 89
arr = [ 100, 3 ]
 
# Function Call
print(minPushes(N, K, arr))
 
# This code is contributed by sanjoy_62.

// C# implementation of the above approach
using System;
 
public class GFG{
 
// Function to find the minimum moves
// to reach K from N
static int minPushes(int N, int K, int[] arr)
{
 
    // Initialization of dp vector
    int[] dp = new int[100000];
    for (int i = 0; i < dp.Length; i++)
        dp[i] = -1;
   
    // dp[i] = minimum pushes
    // required to reach i
    dp[N] = 0;
 
    // Traversing through the buttons
    for (int i = 0; i < arr.Length; i++) {
 
        // Iterating through all the positions
        for (int xx = 0; xx < 100000; xx++) {
            int x = xx;
 
            // If not visited
            if (dp[x] == -1)
                continue;
 
            // Next status of lock
            int next = (x + arr[i]) % 100000;
            while (dp[next] == -1
                   || dp[next] > dp[x] + 1) {
                dp[next] = dp[x] + 1;
 
                // Advance to next state
                x = next;
                next = (next + arr[i]) % 100000;
            }
        }
    }
 
    // Return the readonly dp[target]
    return dp[K];
}
 
// Driver function
public static void Main(String[] args)
{
    // Given Input
    int N = 99880, K = 89;
    int[] arr = { 100, 3 };
 
    // Function Call
    Console.Write(minPushes(N, K, arr));
 
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
        // JavaScript program for the above approach;
 
        // Function to find the minimum moves
        // to reach K from N
        function minPushes(N, K, arr) {
 
            // Initialization of dp vector
            let dp = new Array(100000).fill(-1);
 
            // dp[i] = minimum pushes
            // required to reach i
            dp[N] = 0;
 
            // Traversing through the buttons
            for (let i = 0; i < arr.length; i++) {
 
                // Iterating through all the positions
                for (let xx = 0; xx < 100000; xx++) {
                    let x = xx;
 
                    // If not visited
                    if (dp[x] == -1)
                        continue;
 
                    // Next status of lock
                    let next = (x + arr[i]) % 100000;
                    while (dp[next] == -1
                        || dp[next] > dp[x] + 1) {
                        dp[next] = dp[x] + 1;
 
                        // Advance to next state
                        x = next;
                        next = (next + arr[i]) % 100000;
                    }
                }
            }
 
            // Return the final dp[target]
            return dp[K];
        }
 
        // Driver function
 
        // Given Input
        let N = 99880, K = 89;
        let arr = [100, 3];
 
        // Function Call
        document.write(minPushes(N, K, arr));
 
 
   // This code is contributed by Potta Lokesh
    </script>

5

Complejidad Temporal: O(N*M)
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.