Dada una array de enteros positivos arr[] , la tarea es contar los saltos de factor mínimos necesarios para llegar al final de una array. Desde cualquier índice particular i , el salto se puede realizar solo para índices K donde K es un factor de arr[i] .
Ejemplos:
Entrada: arr[] = {2, 8, 16, 55, 99, 100}
Salida: 2
Explicación:
Los saltos óptimos son:
a) Empezar desde 2.
b) Dado que los factores de 2 son [1, 2]. Por lo tanto, solo están disponibles 1 o 2 saltos de índice. Por lo tanto, salta 1 índice para llegar a 8.
c) Dado que los factores de 8 son [1, 2, 4, 8]. Por lo tanto, solo están disponibles 1, 2, 4 u 8 saltos de índice. Por lo tanto, saltaron 4 índices para llegar a 100.
d) Hemos llegado al final, por lo que no se requieren más saltos.
Entonces, se requirieron 2 saltos.Entrada: arr[] = {2, 4, 6}
Salida: 1
Enfoque: Este problema se puede resolver usando Recursión .
- En primer lugar, necesitamos precalcular los factores de cada número del 1 al 1000000 , para que podamos obtener diferentes opciones de saltos en el tiempo O(1).
- Luego, calcule recursivamente los saltos mínimos necesarios para llegar al final de la array e imprímalo.
C++
// C++ code to count minimum factor jumps
// to reach the end of array
#include <bits/stdc++.h>
using namespace std;
// vector to store factors of each integer
vector<int> factors[100005];
// Precomputing all factors of integers
// from 1 to 100000
void precompute()
{
for (int i = 1; i <= 100000; i++) {
for (int j = i; j <= 100000; j += i) {
factors[j].push_back(i);
}
}
}
// Recursive function to count the minimum jumps
int solve(int arr[], int k, int n)
{
// If we reach the end of array,
// no more jumps are required
if (k == n - 1) {
return 0;
}
// If the jump results in out of index,
// return INT_MAX
if (k >= n) {
return INT_MAX;
}
// Else compute the answer
// using the recurrence relation
int ans = INT_MAX;
// Iterating over all choices of jumps
for (auto j : factors[arr[k]]) {
// Considering current factor as a jump
int res = solve(arr, k + j, n);
// Jump leads to the destination
if (res != INT_MAX) {
ans = min(ans, res + 1);
}
}
// Return ans
return ans;
}
// Driver code
int main()
{
// pre-calculating the factors
precompute();
int arr[] = { 2, 8, 16, 55, 99, 100 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << solve(arr, 0, n);
}
Java
// Java code to count minimum
// factor jumps to reach the
// end of array
import java.util.*;
public class GFG{
// vector to store factors
// of each integer
static Vector<Integer> []factors =
new Vector[100005];
// Precomputing all factors
// of integers from 1 to 100000
static void precompute()
{
for (int i = 0; i < factors.length; i++)
factors[i] = new Vector<Integer>();
for (int i = 1; i <= 100000; i++)
{
for (int j = i; j <= 100000; j += i)
{
factors[j].add(i);
}
}
}
// Function to count the
// minimum jumps
static int solve(int arr[],
int k, int n)
{
// If we reach the end of
// array, no more jumps
// are required
if (k == n - 1)
{
return 0;
}
// If the jump results in
// out of index, return
// Integer.MAX_VALUE
if (k >= n)
{
return Integer.MAX_VALUE;
}
// Else compute the answer
// using the recurrence relation
int ans = Integer.MAX_VALUE;
// Iterating over all choices
// of jumps
for (int j : factors[arr[k]])
{
// Considering current factor
// as a jump
int res = solve(arr, k + j, n);
// Jump leads to the destination
if (res != Integer.MAX_VALUE)
{
ans = Math.min(ans, res + 1);
}
}
// Return ans
return ans;
}
// Driver code
public static void main(String[] args)
{
// pre-calculating
// the factors
precompute();
int arr[] = {2, 8, 16,
55, 99, 100};
int n = arr.length;
System.out.print(solve(arr, 0, n));
}
}
// This code is contributed by Samim Hossain Mondal.
C#
// C# code to count minimum
// factor jumps to reach the
// end of array
using System;
using System.Collections.Generic;
class GFG{
// vector to store factors
// of each integer
static List<int> []factors =
new List<int>[100005];
// Precomputing all factors
// of integers from 1 to 100000
static void precompute()
{
for (int i = 0;
i < factors.Length; i++)
factors[i] = new List<int>();
for (int i = 1; i <= 100000; i++)
{
for (int j = i;
j <= 100000; j += i)
{
factors[j].Add(i);
}
}
}
// Function to count the
// minimum jumps
static int solve(int []arr,
int k, int n)
{
// If we reach the end of
// array, no more jumps
// are required
if (k == n - 1)
{
return 0;
}
// If the jump results in
// out of index, return
// int.MaxValue
if (k >= n)
{
return int.MaxValue;
}
// Else compute the answer
// using the recurrence relation
int ans = int.MaxValue;
// Iterating over all choices
// of jumps
foreach (int j in factors[arr[k]])
{
// Considering current
// factor as a jump
int res = solve(arr, k + j, n);
// Jump leads to the
// destination
if (res != int.MaxValue)
{
ans = Math.Min(ans, res + 1);
}
}
// Return ans
return ans;
}
// Driver code
public static void Main(String[] args)
{
// pre-calculating
// the factors
precompute();
int []arr = {2, 8, 16,
55, 99, 100};
int n = arr.Length;
Console.Write(solve(arr, 0, n));
}
}
// This code is contributed by Samim Hossain Mondal.
Python
# Python3 code to count minimum factor jumps # to reach the end of array # vector to store factors of each integer factors = [[] for i in range(100005)] # Precomputing all factors of integers # from 1 to 100000 def precompute(): for i in range(1, 100001): for j in range(i, 100001, i): factors[j].append(i) # Function to count the minimum jumps def solve(arr, k, n): # If we reach the end of array, # no more jumps are required if (k == n - 1): return 0 # If the jump results in out of index, # return INT_MAX if (k >= n): return 1000000000 # Else compute the answer # using the recurrence relation ans = 1000000000 # Iterating over all choices of jumps for j in factors[arr[k]]: # Considering current factor as a jump res = solve(arr, k + j, n) # Jump leads to the destination if (res != 1000000000): ans = min(ans, res + 1) # Return ans return ans # Driver code if __name__ == '__main__': # pre-calculating the factors precompute() arr = [2, 8, 16, 55, 99, 100] n = len(arr) print(solve(arr, 0, n)) # This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript code to count minimum factor jumps
// to reach the end of array
// vector to store factors of each integer
let factors = new Array();
for (let i = 0; i < 100005; i++) {
factors.push(new Array());
}
// Precomputing all factors of integers
// from 1 to 100000
function precompute() {
for (let i = 1; i <= 100000; i++) {
for (let j = i; j <= 100000; j += i) {
factors[j].push(i);
}
}
}
// Function to count the minimum jumps
function solve(arr, k, n) {
// If we reach the end of array,
// no more jumps are required
if (k == n - 1) {
return 0;
}
// If the jump results in out of index,
// return INT_MAX
if (k >= n) {
return Number.MAX_SAFE_INTEGER;
}
// Else compute the answer
// using the recurrence relation
let ans = Number.MAX_SAFE_INTEGER;
// Iterating over all choices of jumps
for (let j of factors[arr[k]]) {
// Considering current factor as a jump
let res = solve(arr, k + j, n);
// Jump leads to the destination
if (res != Number.MAX_SAFE_INTEGER) {
ans = Math.min(ans, res + 1);
}
}
// Return ans
return ans;
}
// Driver code
// pre-calculating the factors
precompute();
let arr = [2, 8, 16, 55, 99, 100];
let n = arr.length;
document.write(solve(arr, 0, n));
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
2
Complejidad de tiempo: O (100005 * 2 N )
Espacio Auxiliar: O(100005)
Otro Enfoque: Programación Dinámica usando Memoización .
- En primer lugar, necesitamos precalcular los factores de cada número del 1 al 1000000 , para que podamos obtener diferentes opciones de saltos en el tiempo O(1).
- Entonces, sea dp[i] el salto mínimo requerido para alcanzar i, necesitamos encontrar dp[n-1] .
- Entonces, la relación de recurrencia se convierte en:
donde j es uno de los factores de arr[i] & solve() es la función recursiva
![dp[i] = min(dp[i], 1 + solve(i+j))](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-194368907ec895986c58c129a7b4f30c_l3.png "Rendered by QuickLaTeX.com")
- Encuentra los saltos mínimos usando esta relación de recurrencia e imprímela.
A continuación se muestra la implementación recursiva del enfoque anterior:
C++
// C++ code to count minimum factor jumps
// to reach the end of array
#include <bits/stdc++.h>
using namespace std;
// vector to store factors of each integer
vector<int> factors[100005];
// dp array
int dp[100005];
// Precomputing all factors of integers
// from 1 to 100000
void precompute()
{
for (int i = 1; i <= 100000; i++) {
for (int j = i; j <= 100000; j += i) {
factors[j].push_back(i);
}
}
}
// Function to count the minimum jumps
int solve(int arr[], int k, int n)
{
// If we reach the end of array,
// no more jumps are required
if (k == n - 1) {
return 0;
}
// If the jump results in out of index,
// return INT_MAX
if (k >= n) {
return INT_MAX;
}
// If the answer has been already computed,
// return it directly
if (dp[k]) {
return dp[k];
}
// Else compute the answer
// using the recurrence relation
int ans = INT_MAX;
// Iterating over all choices of jumps
for (auto j : factors[arr[k]]) {
// Considering current factor as a jump
int res = solve(arr, k + j, n);
// Jump leads to the destination
if (res != INT_MAX) {
ans = min(ans, res + 1);
}
}
// Return ans and memorize it
return dp[k] = ans;
}
// Driver code
int main()
{
// pre-calculating the factors
precompute();
int arr[] = { 2, 8, 16, 55, 99, 100 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << solve(arr, 0, n);
}
Java
// Java code to count minimum
// factor jumps to reach the
// end of array
import java.util.*;
class GFG{
// vector to store factors
// of each integer
static Vector<Integer> []factors =
new Vector[100005];
// dp array
static int []dp = new int[100005];
// Precomputing all factors
// of integers from 1 to 100000
static void precompute()
{
for (int i = 0; i < factors.length; i++)
factors[i] = new Vector<Integer>();
for (int i = 1; i <= 100000; i++)
{
for (int j = i; j <= 100000; j += i)
{
factors[j].add(i);
}
}
}
// Function to count the
// minimum jumps
static int solve(int arr[],
int k, int n)
{
// If we reach the end of
// array, no more jumps
// are required
if (k == n - 1)
{
return 0;
}
// If the jump results in
// out of index, return
// Integer.MAX_VALUE
if (k >= n)
{
return Integer.MAX_VALUE;
}
// If the answer has been
// already computed, return
// it directly
if (dp[k] != 0)
{
return dp[k];
}
// Else compute the answer
// using the recurrence relation
int ans = Integer.MAX_VALUE;
// Iterating over all choices
// of jumps
for (int j : factors[arr[k]])
{
// Considering current factor
// as a jump
int res = solve(arr, k + j, n);
// Jump leads to the destination
if (res != Integer.MAX_VALUE)
{
ans = Math.min(ans, res + 1);
}
}
// Return ans and memorize it
return dp[k] = ans;
}
// Driver code
public static void main(String[] args)
{
// pre-calculating
// the factors
precompute();
int arr[] = {2, 8, 16,
55, 99, 100};
int n = arr.length;
System.out.print(solve(arr, 0, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 code to count minimum factor jumps # to reach the end of array # vector to store factors of each integer factors= [[] for i in range(100005)]; # dp array dp = [0 for i in range(100005)]; # Precomputing all factors of integers # from 1 to 100000 def precompute(): for i in range(1, 100001): for j in range(i, 100001, i): factors[j].append(i); # Function to count the minimum jumps def solve(arr, k, n): # If we reach the end of array, # no more jumps are required if (k == n - 1): return 0; # If the jump results in out of index, # return INT_MAX if (k >= n): return 1000000000 # If the answer has been already computed, # return it directly if (dp[k]): return dp[k]; # Else compute the answer # using the recurrence relation ans = 1000000000 # Iterating over all choices of jumps for j in factors[arr[k]]: # Considering current factor as a jump res = solve(arr, k + j, n); # Jump leads to the destination if (res != 1000000000): ans = min(ans, res + 1); # Return ans and memorize it dp[k] = ans; return ans # Driver code if __name__=='__main__': # pre-calculating the factors precompute() arr = [ 2, 8, 16, 55, 99, 100 ] n = len(arr) print(solve(arr, 0, n)) # This code is contributed by rutvik_56
C#
// C# code to count minimum
// factor jumps to reach the
// end of array
using System;
using System.Collections.Generic;
class GFG{
// vector to store factors
// of each integer
static List<int> []factors =
new List<int>[100005];
// dp array
static int []dp = new int[100005];
// Precomputing all factors
// of integers from 1 to 100000
static void precompute()
{
for (int i = 0;
i < factors.Length; i++)
factors[i] = new List<int>();
for (int i = 1; i <= 100000; i++)
{
for (int j = i;
j <= 100000; j += i)
{
factors[j].Add(i);
}
}
}
// Function to count the
// minimum jumps
static int solve(int []arr,
int k, int n)
{
// If we reach the end of
// array, no more jumps
// are required
if (k == n - 1)
{
return 0;
}
// If the jump results in
// out of index, return
// int.MaxValue
if (k >= n)
{
return int.MaxValue;
}
// If the answer has been
// already computed, return
// it directly
if (dp[k] != 0)
{
return dp[k];
}
// Else compute the answer
// using the recurrence relation
int ans = int.MaxValue;
// Iterating over all choices
// of jumps
foreach (int j in factors[arr[k]])
{
// Considering current
// factor as a jump
int res = solve(arr, k + j, n);
// Jump leads to the
// destination
if (res != int.MaxValue)
{
ans = Math.Min(ans, res + 1);
}
}
// Return ans and
// memorize it
return dp[k] = ans;
}
// Driver code
public static void Main(String[] args)
{
// pre-calculating
// the factors
precompute();
int []arr = {2, 8, 16,
55, 99, 100};
int n = arr.Length;
Console.Write(solve(arr, 0, n));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript code to count minimum factor jumps
// to reach the end of array
// vector to store factors of each integer
let factors = new Array();
// dp array
let dp = new Array(100005);
for (let i = 0; i < 100005; i++) {
factors.push(new Array());
}
// Precomputing all factors of integers
// from 1 to 100000
function precompute() {
for (let i = 1; i <= 100000; i++) {
for (let j = i; j <= 100000; j += i) {
factors[j].push(i);
}
}
}
// Function to count the minimum jumps
function solve(arr, k, n) {
// If we reach the end of array,
// no more jumps are required
if (k == n - 1) {
return 0;
}
// If the jump results in out of index,
// return INT_MAX
if (k >= n) {
return Number.MAX_SAFE_INTEGER;
}
// If the answer has been already computed,
// return it directly
if (dp[k]) {
return dp[k];
}
// Else compute the answer
// using the recurrence relation
let ans = Number.MAX_SAFE_INTEGER;
// Iterating over all choices of jumps
for (let j of factors[arr[k]]) {
// Considering current factor as a jump
let res = solve(arr, k + j, n);
// Jump leads to the destination
if (res != Number.MAX_SAFE_INTEGER) {
ans = Math.min(ans, res + 1);
}
}
// Return ans and memorize it
return dp[k] = ans;
}
// Driver code
// pre-calculating the factors
precompute();
let arr = [2, 8, 16, 55, 99, 100];
let n = arr.length;
document.write(solve(arr, 0, n));
// This code is contributed by _saurabh_jaiswal
</script>
Producción
2
Complejidad de tiempo: O(100000*N)
Espacio Auxiliar: O(100005)
A continuación se muestra el enfoque ascendente iterativo:
C++
// C++ program for bottom up approach
#include <bits/stdc++.h>
using namespace std;
// Vector to store factors of each integer
vector<int> factors[100005];
// Initialize the dp array
int dp[100005];
// Precompute all the
// factors of every integer
void precompute()
{
for (int i = 1; i <= 100000; i++) {
for (int j = i; j <= 100000; j += i)
factors[j].push_back(i);
}
}
// Function to count the
// minimum factor jump
int solve(int arr[], int n)
{
// Initialise minimum jumps to
// reach each cell as INT_MAX
for (int i = 0; i <= 100005; i++) {
dp[i] = INT_MAX;
}
// 0 jumps required to
// reach the first cell
dp[0] = 0;
// Iterate over all cells
for (int i = 0; i < n; i++) {
// calculating for each jump
for (auto j : factors[arr[i]]) {
// If a cell is in bound
if (i + j < n)
dp[i + j] = min(dp[i + j], 1 + dp[i]);
}
}
// Return minimum jumps
// to reach last cell
return dp[n - 1];
}
// Driver code
int main()
{
// Pre-calculating the factors
precompute();
int arr[] = { 2, 8, 16, 55, 99, 100 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << solve(arr, n);
}
Java
// Java program for bottom up approach
import java.util.*;
class GFG{
// Vector to store factors of each integer
@SuppressWarnings("unchecked")
static Vector<Integer> []factors = new Vector[100005];
// Initialize the dp array
static int []dp = new int[100005];
// Precompute all the
// factors of every integer
static void precompute()
{
for(int i = 1; i <= 100000; i++)
{
for(int j = i; j <= 100000; j += i)
factors[j].add(i);
}
}
// Function to count the
// minimum factor jump
static int solve(int arr[], int n)
{
// Initialise minimum jumps to
// reach each cell as Integer.MAX_VALUE
for(int i = 0; i < 100005; i++)
{
dp[i] = Integer.MAX_VALUE;
}
// 0 jumps required to
// reach the first cell
dp[0] = 0;
// Iterate over all cells
for(int i = 0; i < n; i++)
{
// Calculating for each jump
for(int j : factors[arr[i]])
{
// If a cell is in bound
if (i + j < n)
dp[i + j] = Math.min(dp[i + j],
1 + dp[i]);
}
}
// Return minimum jumps
// to reach last cell
return dp[n - 1];
}
// Driver code
public static void main(String[] args)
{
for(int i = 0; i < factors.length; i++)
factors[i] = new Vector<Integer>();
// Pre-calculating the factors
precompute();
int arr[] = { 2, 8, 16, 55, 99, 100 };
int n = arr.length;
// Function call
System.out.print(solve(arr, n));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for bottom up approach # Vector to store factors of each integer factors=[[] for i in range(100005)]; # Initialize the dp array dp=[1000000000 for i in range(100005)]; # Precompute all the # factors of every integer def precompute(): for i in range(1, 100001): for j in range(i, 100001, i): factors[j].append(i); # Function to count the # minimum factor jump def solve(arr, n): # 0 jumps required to # reach the first cell dp[0] = 0; # Iterate over all cells for i in range(n): # calculating for each jump for j in factors[arr[i]]: # If a cell is in bound if (i + j < n): dp[i + j] = min(dp[i + j], 1 + dp[i]); # Return minimum jumps # to reach last cell return dp[n - 1]; # Driver code if __name__=='__main__': # Pre-calculating the factors precompute(); arr = [ 2, 8, 16, 55, 99, 100 ] n=len(arr) # Function call print(solve(arr,n)) # This code is contributed by pratham76
C#
// C# program for bottom up approach
using System;
using System.Collections.Generic;
class GFG{
// Vector to store factors of each integer
static List<List<int>> factors = new List<List<int>>();
// Initialize the dp array
static int[] dp;
// Precompute all the
// factors of every integer
static void precompute()
{
for(int i = 1; i <= 100000; i++)
{
for(int j = i; j <= 100000; j += i)
factors[j].Add(i);
}
}
// Function to count the
// minimum factor jump
static int solve(int[] arr, int n)
{
// Initialise minimum jumps to
// reach each cell as Integer.MAX_VALUE
for(int i = 0; i < 100005; i++)
{
dp[i] = int.MaxValue;
}
// 0 jumps required to
// reach the first cell
dp[0] = 0;
// Iterate over all cells
for(int i = 0; i < n; i++)
{
// Calculating for each jump
foreach(int j in factors[arr[i]])
{
// If a cell is in bound
if (i + j < n)
dp[i + j] = Math.Min(dp[i + j],
1 + dp[i]);
}
}
// Return minimum jumps
// to reach last cell
return dp[n - 1];
}
// Driver code
static public void Main ()
{
for(int i = 0; i < 100005; i++)
factors.Add(new List<int>());
dp = new int[100005];
// Pre-calculating the factors
precompute();
int[] arr = { 2, 8, 16, 55, 99, 100 };
int n = arr.Length;
// Function call
Console.Write(solve(arr, n));
}
}
// This code is contributed by offbeat
Javascript
<script>
// Javascript program for bottom up approach
// Vector to store factors of each integer
var factors = Array.from(Array(100005), ()=>Array());
// Initialize the dp array
var dp = Array(100005);
// Precompute all the
// factors of every integer
function precompute()
{
for (var i = 1; i <= 100000; i++) {
for (var j = i; j <= 100000; j += i)
factors[j].push(i);
}
}
// Function to count the
// minimum factor jump
function solve(arr, n)
{
// Initialise minimum jumps to
// reach each cell as INT_MAX
for (var i = 0; i <= 100005; i++) {
dp[i] = 1000000000;
}
// 0 jumps required to
// reach the first cell
dp[0] = 0;
// Iterate over all cells
for (var i = 0; i < n; i++) {
// calculating for each jump
for (var j of factors[arr[i]]) {
// If a cell is in bound
if (i + j < n)
dp[i + j] = Math.min(dp[i + j], 1 + dp[i]);
}
}
// Return minimum jumps
// to reach last cell
return dp[n - 1];
}
// Driver code
// Pre-calculating the factors
precompute();
var arr = [2, 8, 16, 55, 99, 100];
var n = arr.length
// Function call
document.write( solve(arr, n));
</script>
Producción
2
Complejidad del tiempo: O(N 2 )
Espacio Auxiliar: O(100005)
Publicación traducida automáticamente
Artículo escrito por VikasVishwakarma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA