Dada una array de longitud infinita y dos enteros M y N que son coprimos, la tarea es encontrar el número de posiciones que no se pueden visitar a partir de la primera posición cuando en un solo movimiento desde arr[i] , ya sea arr[ Se puede llegar a i + M] o arr[i + N] . Tenga en cuenta que el resultado siempre es finito.
Ejemplos :
Entrada: M = 2, N = 5
Salida: 2
A partir del índice 0, los índices que se pueden visitar son
0 + 2 = 2
0 + 2 + 2 = 4
0 + 5 = 5
0 + 2 + 2 + 2 = 6
0 + 2 + 5 = 7
0 + 2 + 2 + 2 + 2 = 8
0 + 2 + 2 + 5 = 9
0 + 5 + 5 = 10
…
1 y 3 son los únicos índices que no se pueden visitar.
Entrada: M = 5, N = 6
Salida: 15
Acercarse:
- Encuentre el índice más grande que no se puede obtener usando ninguna combinación de M & N usando el número de Frobenius , digamos X = (M * N) – M – N.
- Dado que X es el índice más grande que no se puede visitar, no es necesario verificar cada índice mayor que él.
- Ahora, para los índices más pequeños que X , si X no se visita, entonces Y = X – M y Z = X – N también son inalcanzables y lo mismo ocurre con Y – M y Z – N y así sucesivamente… hasta que los índices sean mayores que 0 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count // of unvisited indices starting // from the index 0 int countUnvisited(int n, int m) { // Largest index that // cannot be visited int X = (m * n) - m - n; // Push the index to the queue queue<int> queue; queue.push(X); // To store the required count int count = 0; while (queue.size() > 0) { // Current index that cannot be visited int curr = queue.front(); queue.pop(); // Increment the count for // the current index count++; // (curr - m) and (curr - n) are also // unreachable if they are valid indices if (curr - m > 0) queue.push(curr - m); if (curr - n > 0) queue.push(curr - n); } // Return the required count return count; } // Driver code int main() { int n = 2, m = 5; cout << countUnvisited(n, m); return 0; } // This code is contributed by Sanjit_Prasad
Java
// Java implementation of the approach import java.util.LinkedList; import java.util.Queue; class GFG { // Function to return the count // of unvisited indices starting // from the index 0 public static int countUnvisited(int n, int m) { // Largest index that // cannot be visited int X = (m * n) - m - n; // Push the index to the queue Queue<Integer> queue = new LinkedList<>(); queue.add(X); // To store the required count int count = 0; while (!queue.isEmpty()) { // Current index that cannot be visited int curr = queue.poll(); // Increment the count for // the current index count++; // (curr - m) and (curr - n) are also // unreachable if they are valid indices if (curr - m > 0) queue.add(curr - m); if (curr - n > 0) queue.add(curr - n); } // Return the required count return count; } // Driver code public static void main(String args[]) { int n = 2, m = 5; System.out.print(countUnvisited(n, m)); } }
Python 3
# Python 3 implementation of the approach # Function to return the count # of unvisited indices starting # from the index 0 def countUnvisited(n, m): # Largest index that # cannot be visited i = 0 X = (m * n) - m - n # Push the index to the queue queue = [] queue.append(X) # To store the required count count = 0 while (len(queue) > 0): # Current index that cannot be visited curr = queue[0] queue.remove(queue[0]) # Increment the count for # the current index count += 1 # (curr - m) and (curr - n) are also # unreachable if they are valid indices if (curr - m > 0): queue.append(curr - m) if (curr - n > 0): queue.append(curr - n) # Return the required count return count # Driver code if __name__ == '__main__': n = 2 m = 5 print(countUnvisited(n, m)) # This code is contributed by Surendra_Gangwar
C#
// C# implementation of the above approach using System; using System.Collections.Generic; class GFG { // Function to return the count // of unvisited indices starting // from the index 0 public static int countUnvisited(int n, int m) { // Largest index that // cannot be visited int X = (m * n) - m - n; // Push the index to the queue Queue<int> queue = new Queue<int>(); queue.Enqueue(X); // To store the required count int count = 0; while (queue.Count != 0) { // Current index that cannot be visited int curr = queue.Dequeue(); // Increment the count for // the current index count++; // (curr - m) and (curr - n) are also // unreachable if they are valid indices if (curr - m > 0) queue.Enqueue(curr - m); if (curr - n > 0) queue.Enqueue(curr - n); } // Return the required count return count; } // Driver code public static void Main(String []args) { int n = 2, m = 5; Console.WriteLine(countUnvisited(n, m)); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // JavaScript implementation of the approach // Function to return the count // of unvisited indices starting // from the index 0 function countUnvisited(n, m) { // Largest index that // cannot be visited let X = (m * n) - m - n; // Push the index to the queue let queue = []; queue.push(X); // To store the required count let count = 0; while (queue.length > 0) { // Current index that cannot be visited let curr = queue[0]; queue.pop(); // Increment the count for // the current index count++; // (curr - m) and (curr - n) are also // unreachable if they are valid indices if (curr - m > 0) queue.push(curr - m); if (curr - n > 0) queue.push(curr - n); } // Return the required count return count; } // Driver code let n = 2, m = 5; document.write(countUnvisited(n, m)); // This code is contributed by shinjanpatra </script>
2
Complejidad temporal: O(n * m)
Espacio Auxiliar: O(1)