Dada una array mat[][] de dimensión NxM , la tarea es contar el número de rutas únicas desde la celda superior izquierda, es decir, mat[0][0] , hasta la celda inferior derecha, es decir, mat[N – 1][M – 1] de la array dada tal que el producto de los elementos en ese camino contiene un número impar de divisores . Los movimientos posibles desde cualquier celda (i, j) son (i, j + 1) o (i + 1, j) .
Ejemplos:
Entrada: mat[][] = {{1, 1}, {3, 1}, {3, 1}}
Salida: 2
Explicación: Dos caminos posibles que satisfacen la condición:
- 1->3->3->1, Producto = 9, Número de divisores de 9 son 1, 3, 9 que es impar.
- 1->1->1->1, Producto = 1, Número de divisores de 1 es solo 1, lo que es impar.
Entrada: mat[][] = {{4, 1}, {4, 4}}
Salida: 2
Explicación: Dos caminos posibles que satisfacen la condición:
- 4->4->4, Producto = 64, Número de divisores de 9 son 1, 2, 4, 8, 16, 32, 64 que es impar.
- 4->1->4, Producto = 16, Número de divisores de 16 son 1, 2, 4, 8, 16 que es impar.
Enfoque ingenuo: el enfoque más simple es generar todas las rutas posibles desde la celda superior izquierda hasta la celda inferior derecha para la array dada y verificar si el producto de todos los elementos para todas esas rutas tiene un número impar de divisores al encontrar todos los divisores usando el enfoque discutido en este artículo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int countPaths = 0;
// Store the product of all paths
vector<int> v;
// Function to calculate and store
// all the paths product in vector
void CountUniquePaths(int a[][105], int i,
int j, int m,
int n, int ans)
{
// Base Case
if (i >= m || j >= n)
return;
// If reaches the bottom right
// corner and product is a
// perfect square
if (i == m - 1 && j == n - 1) {
// Find square root
long double sr = sqrt(ans * a[i][j]);
// If square root is an integer
if ((sr - floor(sr)) == 0)
countPaths++;
}
// Move towards down in the matrix
CountUniquePaths(a, i + 1, j, m,
n, ans * a[i][j]);
// Move towards right in the matrix
CountUniquePaths(a, i, j + 1, m,
n, ans * a[i][j]);
}
// Driver Code
int main()
{
int M = 3, N = 2;
// Given matrix mat[][]
int mat[M][105] = { { 1, 1 },
{ 3, 1 },
{ 3, 1 } };
// Function Call
CountUniquePaths(mat, 0, 0, M, N, 1);
// Print the result
cout << countPaths;
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG{
static int countPaths = 0;
// Function to calculate and store
// all the paths product in vector
static void CountUniquePaths(int[][] a, int i,
int j, int m,
int n, int ans)
{
// Base Case
if (i >= m || j >= n)
return;
// If reaches the bottom right
// corner and product is a
// perfect square
if (i == m - 1 && j == n - 1)
{
// Find square root
double sr = Math.sqrt(ans * a[i][j]);
// If square root is an integer
if ((sr - Math.floor(sr)) == 0)
countPaths++;
}
// Move towards down in the matrix
CountUniquePaths(a, i + 1, j, m,
n, ans * a[i][j]);
// Move towards right in the matrix
CountUniquePaths(a, i, j + 1, m,
n, ans * a[i][j]);
}
// Driver Code
public static void main (String[] args)
{
int M = 3, N = 2;
// Given matrix mat[][]
int[][] mat = { { 1, 1 },
{ 3, 1 },
{ 3, 1 } };
// Function call
CountUniquePaths(mat, 0, 0, M, N, 1);
System.out.println(countPaths);
}
}
// This code is contributed by sallagondaavinashreddy7
Python3
# Python3 program for # the above approach import math countPaths = 0; # Function to calculate # and store all the paths # product in vector def CountUniquePaths(a, i, j, m, n, ans): # Base Case if (i >= m or j >= n): return; # If reaches the bottom # right corner and product # is a perfect square global countPaths; if (i == m - 1 and j == n - 1): # Find square root sr = math.sqrt(ans * a[i][j]); # If square root is an integer if ((sr - math.floor(sr)) == 0): countPaths += 1; # Move towards down # in the matrix CountUniquePaths(a, i + 1, j, m, n, ans * a[i][j]); # Move towards right # in the matrix CountUniquePaths(a, i, j + 1, m, n, ans * a[i][j]); # Driver Code if __name__ == '__main__': M = 3; N = 2; # Given matrix mat mat = [[1, 1], [3, 1], [3, 1]]; # Function call CountUniquePaths(mat, 0, 0, M, N, 1); print(countPaths); # This code is contributed by Princi Singh
C#
// C# program for the
// above approach
using System;
class GFG{
static int countPaths = 0;
// Function to calculate and store
// all the paths product in vector
static void CountUniquePaths(int[,] a, int i,
int j, int m,
int n, int ans)
{
// Base Case
if (i >= m || j >= n)
return;
// If reaches the bottom right
// corner and product is a
// perfect square
if (i == m - 1 && j == n - 1)
{
// Find square root
double sr = Math.Sqrt(ans *
a[i, j]);
// If square root is an integer
if ((sr - Math.Floor(sr)) == 0)
countPaths++;
}
// Move towards down in the matrix
CountUniquePaths(a, i + 1, j, m,
n, ans * a[i, j]);
// Move towards right in the matrix
CountUniquePaths(a, i, j + 1, m,
n, ans * a[i, j]);
}
// Driver Code
public static void Main (String[] args)
{
int M = 3, N = 2;
// Given matrix mat[][]
int[,] mat = {{1, 1},
{3, 1},
{3, 1}};
// Function call
CountUniquePaths(mat, 0, 0,
M, N, 1);
Console.Write(countPaths);
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// Javascript program for the
// above approach
let countPaths = 0;
// Function to calculate and store
// all the paths product in vector
function CountUniquePaths(a, i, j, m, n, ans)
{
// Base Case
if (i >= m || j >= n)
return;
// If reaches the bottom right
// corner and product is a
// perfect square
if (i == m - 1 && j == n - 1)
{
// Find square root
let sr = Math.sqrt(ans * a[i][j]);
// If square root is an integer
if ((sr - Math.floor(sr)) == 0)
countPaths++;
}
// Move towards down in the matrix
CountUniquePaths(a, i + 1, j, m,
n, ans * a[i][j]);
// Move towards right in the matrix
CountUniquePaths(a, i, j + 1, m,
n, ans * a[i][j]);
}
// Driver Code
let M = 3, N = 2;
// Given matrix mat[][]
let mat = [ [ 1, 1 ],
[ 3, 1 ],
[ 3, 1 ] ];
// Function call
CountUniquePaths(mat, 0, 0, M, N, 1);
document.write(countPaths);
// This code is contributed by souravghosh0416
</script>
Producción:
2
Complejidad de tiempo: O((2 N )*sqrt(N))
Espacio auxiliar: O(1)
Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es utilizar Programación Dinámica . Inicialice un espacio auxiliar dp[][][] que almacenará los números que tienen un producto de todo el camino desde la parte superior izquierda hasta el final de cada fila para cada fila de la array dada. A continuación se muestran los pasos:
- Inicialice un espacio auxiliar 3D dp[][][] donde dp[i][j] almacenará el producto de toda la ruta desde la celda (0, 0) a (i, j) .
- Para calcular los valores de cada estado, calcule dp[i][j] usando todos los valores de dp(i – 1, j) y dp(i, j – 1) .
- Para la primera fila de la array dada mat[][], almacene el prefijo producto de la primera fila en dp[i][0] .
- Para la primera columna de la array dada mat[][], almacene el prefijo producto de la primera columna en dp[0][i] .
- Ahora itere sobre (1, 1) a (N, M) usando dos bucles anidados i y j y haga lo siguiente:
- Guarde la parte superior del vector en el índice dp[i – 1][j] y a la izquierda en el índice dp[i][j – 1] .
- Almacene el producto del elemento actual mat[i][j] con los elementos almacenados en top[] y left[] en otra array auxiliar curr[] .
- Actualice el estado actual de dp como dp[i][j] = curr .
- Ahora recorra la array almacenada en dp(N – 1, M – 1) y cuente todos los números que es un cuadrado perfecto .
- Imprima el recuento final después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the results
vector<vector<vector<int> > >
dp(105, vector<vector<int> >(105));
// Count of unique product paths
int countPaths = 0;
// Function to check whether number
// is perfect square or not
bool isPerfectSquare(int n)
{
long double sr = sqrt(n);
// If square root is an integer
return ((sr - floor(sr)) == 0);
}
// Function to calculate and store
// all the paths product in vector
void countUniquePaths(int a[][105],
int m, int n,
int ans)
{
// Store the value a[0][0]
dp[0][0].push_back(a[0][0]);
// Initialize first row of dp
for (int i = 1; i < m; i++) {
// Find prefix product
a[i][0] *= a[i - 1][0];
dp[i][0].push_back(a[i][0]);
}
// Initialize first column of dp
for (int i = 1; i < n; i++) {
// Find the prefix product
a[0][i] *= a[0][i - 1];
dp[0][i].push_back(a[0][i]);
}
// Iterate over range (1, 1) to (N, M)
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// Copy dp[i-1][j] in top[]
vector<int> top = dp[i - 1][j];
// Copy dp[i][j-1] into left[]
vector<int> left = dp[i][j - 1];
// Compute the values of current
// state and store it in curr[]
vector<int> curr;
// Find the product of a[i][j]
// with elements at top[]
for (int k = 0;
k < top.size(); k++) {
curr.push_back(top[k] * a[i][j]);
}
// Find the product of a[i][j]
// with elements at left[]
for (int k = 0;
k < left.size(); k++) {
curr.push_back(left[k] * a[i][j]);
}
// Update the current state
dp[i][j] = curr;
}
}
// Traverse dp[m - 1][n - 1]
for (auto i : dp[m - 1][n - 1]) {
// Check if perfect square
if (isPerfectSquare(i)) {
countPaths++;
}
}
}
// Driver Code
int main()
{
int M = 3, N = 4;
// Given matrix mat[][]
int mat[M][105] = { { 1, 2, 3, 1 },
{ 3, 1, 2, 4 },
{ 2, 3, 1, 1 } };
// Function Call
countUniquePaths(mat, M, N, 1);
// Print the final count
cout << countPaths;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Stores the results
static ArrayList<ArrayList<ArrayList<Integer>>> dp;
// Count of unique product paths
static int countPaths = 0;
// Function to check whether number
// is perfect square or not
static boolean isPerfectSquare(int n)
{
double sr = Math.sqrt(n);
// If square root is an integer
return ((sr - Math.floor(sr)) == 0);
}
// Function to calculate and store
// all the paths product in vector
static void countUniquePaths(int a[][],
int m, int n,
int ans)
{
// Store the value a[0][0]
dp.get(0).get(0).add(a[0][0]);
// Initialize first row of dp
for (int i = 1; i < m; i++)
{
// Find prefix product
a[i][0] *= a[i - 1][0];
dp.get(i).get(0).add(a[i][0]);
}
// Initialize first column of dp
for (int i = 1; i < n; i++)
{
// Find the prefix product
a[0][i] *= a[0][i - 1];
dp.get(0).get(i).add(a[0][i]);
}
// Iterate over range (1, 1) to (N, M)
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
// Copy dp[i-1][j] in top[]
ArrayList<Integer> top =
dp.get(i - 1).get(j);
// Copy dp[i][j-1] into left[]
ArrayList<Integer> left =
dp.get(i).get(j - 1);
// Compute the values of current
// state and store it in curr[]
ArrayList<Integer> curr = new ArrayList<>();
// Find the product of a[i][j]
// with elements at top[]
for (int k = 0;
k < top.size(); k++)
{
curr.add(top.get(k) * a[i][j]);
}
// Find the product of a[i][j]
// with elements at left[]
for (int k = 0;
k < left.size(); k++)
{
curr.add(left.get(k) * a[i][j]);
}
// Update the current state
dp.get(i).set(j, curr);
}
}
// Traverse dp[m - 1][n - 1]
for (Integer i : dp.get(m - 1).get(n - 1))
{
// Check if perfect square
if (isPerfectSquare(i))
{
countPaths++;
}
}
}
// Driver code
public static void main (String[] args)
{
int M = 3, N = 4;
// Given matrix mat[][]
int mat[][] = { { 1, 2, 3, 1 },
{ 3, 1, 2, 4 },
{ 2, 3, 1, 1 } };
dp = new ArrayList<>();
for(int i = 0; i < 105; i++)
{
dp.add(new ArrayList<>());
for(int j = 0; j < 105; j++)
dp.get(i).add(new ArrayList<Integer>());
}
// Function Call
countUniquePaths(mat, M, N, 1);
// Print the final count
System.out.println(countPaths);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach from math import sqrt, floor # Stores the results dp = [[[] for j in range(105)] for k in range(105)] # Count of unique product paths countPaths = 0 # Function to check whether number # is perfect square or not def isPerfectSquare(n): sr = sqrt(n) # If square root is an integer return ((sr - floor(sr)) == 0) # Function to calculate and store # all the paths product in vector def countUniquePaths(a, m, n, ans): global dp global countPaths # Store the value a[0][0] dp[0][0].append(a[0][0]) # Initialize first row of dp for i in range(1, m): # Find prefix product a[i][0] *= a[i - 1][0] dp[i][0].append(a[i][0]) # Initialize first column of dp for i in range(1, n): # Find the prefix product a[0][i] *= a[0][i - 1] dp[0][i].append(a[0][i]) # Iterate over range (1, 1) to (N, M) for i in range(1, m): for j in range(1, n): # Copy dp[i-1][j] in top[] top = dp[i - 1][j] # Copy dp[i][j-1] into left[] left = dp[i][j - 1] # Compute the values of current # state and store it in curr[] curr = [] # Find the product of a[i][j] # with elements at top[] for k in range(len(top)): curr.append(top[k] * a[i][j]) # Find the product of a[i][j] # with elements at left[] for k in range(len(left)): curr.append(left[k] * a[i][j]) # Update the current state dp[i][j] = curr # Traverse dp[m - 1][n - 1] for i in dp[m - 1][n - 1]: # Check if perfect square if (isPerfectSquare(i)): countPaths += 1 # Driver Code if __name__ == '__main__': M = 3 N = 4 # Given matrix mat[][] mat = [ [ 1, 2, 3, 1 ], [ 3, 1, 2, 4 ], [ 2, 3, 1, 1 ] ] # Function Call countUniquePaths(mat, M, N, 1) # Print the final count print(countPaths) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Stores the results
static List<List<List<int>>> dp;
// Count of unique product paths
static int countPaths = 0;
// Function to check whether number
// is perfect square or not
static bool isPerfectSquare(int n)
{
double sr = Math.Sqrt(n);
// If square root is an integer
return ((sr - Math.Floor(sr)) == 0);
}
// Function to calculate and store
// all the paths product in vector
static void countUniquePaths(int[,] a,
int m, int n,
int ans)
{
// Store the value a[0][0]
dp[0][0].Add(a[0, 0]);
// Initialize first row of dp
for (int i = 1; i < m; i++)
{
// Find prefix product
a[i, 0] *= a[i - 1, 0];
dp[i][0].Add(a[i, 0]);
}
// Initialize first column of dp
for (int i = 1; i < n; i++)
{
// Find the prefix product
a[0, i] *= a[0, i - 1];
dp[0][i].Add(a[0, i]);
}
// Iterate over range (1, 1) to (N, M)
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
// Copy dp[i-1][j] in top[]
List<int> top = dp[i - 1][j];
// Copy dp[i][j-1] into left[]
List<int> left = dp[i][j - 1];
// Compute the values of current
// state and store it in curr[]
List<int> curr = new List<int>();
// Find the product of a[i][j]
// with elements at top[]
for (int k = 0;
k < top.Count; k++)
{
curr.Add(top[k] * a[i, j]);
}
// Find the product of a[i][j]
// with elements at left[]
for (int k = 0;
k < left.Count; k++)
{
curr.Add(left[k] * a[i, j]);
}
// Update the current state
dp[i][j] = curr;
}
}
// Traverse dp[m - 1][n - 1]
foreach (int i in dp[m - 1][n - 1])
{
// Check if perfect square
if (isPerfectSquare(i))
{
countPaths++;
}
}
}
// Driver code
public static void Main()
{
int M = 3, N = 4;
// Given matrix mat[][]
int[,] mat = { { 1, 2, 3, 1 },
{ 3, 1, 2, 4 },
{ 2, 3, 1, 1 } };
dp = new List<List<List<int>>>();
for (int i = 0; i < 105; i++)
{
dp.Add(new List<List<int>>());
for (int j = 0; j < 105; j++)
dp[i].Add(new List<int>());
}
// Function Call
countUniquePaths(mat, M, N, 1);
// Print the final count
Console.Write(countPaths);
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// Javascript program for the above approach
// Stores the results
let dp = [];
// Count of unique product paths
let countPaths = 0;
// Function to check whether number
// is perfect square or not
function isPerfectSquare(n)
{
let sr = Math.sqrt(n);
// If square root is an integer
return((sr - Math.floor(sr)) == 0);
}
// Function to calculate and store
// all the paths product in vector
function countUniquePaths(a, m, n, ans)
{
// Store the value a[0][0]
dp[0][0].push(a[0][0]);
// Initialize first row of dp
for(let i = 1; i < m; i++)
{
// Find prefix product
a[i][0] *= a[i - 1][0];
dp[i][0].push(a[i][0]);
}
// Initialize first column of dp
for(let i = 1; i < n; i++)
{
// Find the prefix product
a[0][i] *= a[0][i - 1];
dp[0][i].push(a[0][i]);
}
// Iterate over range (1, 1) to (N, M)
for(let i = 1; i < m; i++)
{
for(let j = 1; j < n; j++)
{
// Copy dp[i-1][j] in top[]
let top = dp[i - 1][j];
// Copy dp[i][j-1] into left[]
let left = dp[i][j - 1];
// Compute the values of current
// state and store it in curr[]
let curr = [];
// Find the product of a[i][j]
// with elements at top[]
for(let k = 0; k < top.length; k++)
{
curr.push(top[k] * a[i][j]);
}
// Find the product of a[i][j]
// with elements at left[]
for(let k = 0; k < left.length; k++)
{
curr.push(left[k] * a[i][j]);
}
// Update the current state
dp[i][j] = curr;
}
}
// Traverse dp[m - 1][n - 1]
for(let i = 0; i < dp[m - 1][n - 1].length; i++)
{
// Check if perfect square
if (isPerfectSquare(dp[m - 1][n - 1][i]))
{
countPaths++;
}
}
}
// Driver code
let M = 3, N = 4;
let mat = [ [ 1, 2, 3, 1 ],
[ 3, 1, 2, 4 ],
[ 2, 3, 1, 1 ] ];
for(let i = 0; i < 105; i++)
{
dp.push([]);
for(let j = 0; j < 105; j++)
dp[i].push([]);
}
// Function Call
countUniquePaths(mat, M, N, 1);
// Print the final count
document.write(countPaths);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N 3 )
Publicación traducida automáticamente
Artículo escrito por bolliranadheer y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA