Dada una array M x N mat[][] . La tarea es contar el número de celdas buenas en la array. Una celda será buena si la suma del valor de la celda y el número de celdas adyacentes es un número de Fibonacci.
Ejemplos:
Entrada: mat[][] = {
{1, 2},
{3, 4}}
Salida: 2
Solo las celdas mat[0][0] y mat[1][0] son buenas.
es decir, (1 + 2) = 3 y (3 + 2) = 5 son números de Fibonacci.
Entrada: mat[][] = {
{1, 0, 5, 3},
{2, 17, 5, 6},
{5, 8, 15, 11}};
Salida: 7
Enfoque: iterar toda la array y para cada celda encontrar el recuento de celdas adyacentes. Puede haber 3 tipos de celdas, uno con 2 celdas adyacentes, uno con 3 celdas adyacentes y el resto con 4 celdas adyacentes. Sume este recuento con el valor de la celda actual y compruebe si el resultado es un número de Fibonacci. Si es así, entonces incremente el conteo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define M 3
#define N 4
// Function that returns true if
// x is a perfect square
bool isPerfectSquare(long double x)
{
// Find floating point value of
// square root of x
long double sr = sqrt(x);
// If square root is an integer
return ((sr - floor(sr)) == 0);
}
// Function that returns true
// if n is a Fibonacci number
bool isFibonacci(int n)
{
return isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4);
}
// Function to return the count of good cells
int goodCells(int mat[M][N])
{
// To store the required count
int count = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
int sum = mat[i][j];
// Corner cells of the matrix
// have only 2 adjacent cells
if ((i == 0 && j == 0)
|| (i == M - 1 && j == 0)
|| (i == 0 && j == N - 1)
|| (i == M - 1 && j == N - 1)) {
sum += 2;
}
// All the boundary elements
// except the corner elements
// have only 3 adjacent cells
else if (i == 0 || j == 0
|| i == M - 1 || j == N - 1) {
sum += 3;
}
// Rest of the elements have 4 adjacent cells
else {
sum += 4;
}
// If the sum is a Fibonacci number
if (isFibonacci(sum))
count++;
}
}
return count;
}
// Driver code
int main()
{
int mat[M][N] = { { 1, 0, 5, 3 },
{ 2, 17, 5, 6 },
{ 5, 8, 15, 11 } };
cout << goodCells(mat);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG
{
static int M = 3;
static int N = 4;
// Function that returns true if
// x is a perfect square
static boolean isPerfectSquare(long x)
{
// Find floating point value of
// square root of x
double sr = Math.sqrt(x);
// If square root is an integer
return ((sr - Math.floor(sr)) == 0);
}
// Function that returns true
// if n is a Fibonacci number
static boolean isFibonacci(int n)
{
return isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4);
}
// Function to return the count of good cells
static int goodCells(int mat[][])
{
// To store the required count
int count = 0;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
int sum = mat[i][j];
// Corner cells of the matrix
// have only 2 adjacent cells
if ((i == 0 && j == 0)
|| (i == M - 1 && j == 0)
|| (i == 0 && j == N - 1)
|| (i == M - 1 && j == N - 1))
{
sum += 2;
}
// All the boundary elements
// except the corner elements
// have only 3 adjacent cells
else if (i == 0 || j == 0
|| i == M - 1 || j == N - 1)
{
sum += 3;
}
// Rest of the elements have 4 adjacent cells
else
{
sum += 4;
}
// If the sum is a Fibonacci number
if (isFibonacci(sum))
count++;
}
}
return count;
}
// Driver code
public static void main (String[] args)
{
int mat[][] = { { 1, 0, 5, 3 },
{ 2, 17, 5, 6 },
{ 5, 8, 15, 11 } };
System.out.println( goodCells(mat));
}
}
// This code is contributed by anuj_67..
Python
# Python implementation of the approach from math import ceil,sqrt,floor M = 3 N = 4 # Function that returns true if # x is a perfect square def isPerfectSquare(x): # Find floating povalue of # square root of x sr = (sqrt(x)) # If square root is an integer return ((sr - floor(sr)) == 0) # Function that returns true # if n is a Fibonacci number def isFibonacci(n): return isPerfectSquare(5 * n * n + 4) or isPerfectSquare(5 * n * n - 4) # Function to return the count of good cells def goodCells(mat): # To store the required count count = 0 for i in range(M): for j in range(N): sum = mat[i][j] # Corner cells of the matrix # have only 2 adjacent cells if ((i == 0 and j == 0) or (i == M - 1 and j == 0) or (i == 0 and j == N - 1) or (i == M - 1 and j == N - 1)): sum += 2 # All the boundary elements # except the corner elements # have only 3 adjacent cells elif (i == 0 or j == 0 or i == M - 1 or j == N - 1): sum += 3 # Rest of the elements have 4 adjacent cells else: sum += 4 # If the sum is a Fibonacci number if (isFibonacci(sum)): count += 1 return count # Driver code mat = [ [ 1, 0, 5, 3 ], [ 2, 17, 5, 6 ], [ 5, 8, 15, 11 ] ] print(goodCells(mat)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
static int M = 3;
static int N = 4;
// Function that returns true if
// x is a perfect square
static bool isPerfectSquare(long x)
{
// Find floating point value of
// square root of x
double sr = Math.Sqrt(x);
// If square root is an integer
return ((sr - Math.Floor(sr)) == 0);
}
// Function that returns true
// if n is a Fibonacci number
static bool isFibonacci(int n)
{
return isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4);
}
// Function to return the count of good cells
static int goodCells(int [,]mat)
{
// To store the required count
int count = 0;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
int sum = mat[i,j];
// Corner cells of the matrix
// have only 2 adjacent cells
if ((i == 0 && j == 0)
|| (i == M - 1 && j == 0)
|| (i == 0 && j == N - 1)
|| (i == M - 1 && j == N - 1))
{
sum += 2;
}
// All the boundary elements
// except the corner elements
// have only 3 adjacent cells
else if (i == 0 || j == 0
|| i == M - 1 || j == N - 1)
{
sum += 3;
}
// Rest of the elements have 4 adjacent cells
else
{
sum += 4;
}
// If the sum is a Fibonacci number
if (isFibonacci(sum))
count++;
}
}
return count;
}
// Driver code
public static void Main ()
{
int [,]mat = { { 1, 0, 5, 3 },
{ 2, 17, 5, 6 },
{ 5, 8, 15, 11 } };
Console.WriteLine( goodCells(mat));
}
}
// This code is contributed by anuj_67..
Javascript
<script>
// Javascript implementation of the approach
let M = 3;
let N = 4;
// Function that returns true if
// x is a perfect square
function isPerfectSquare(x)
{
// Find floating point value of
// square root of x
let sr = Math.sqrt(x);
// If square root is an integer
return ((sr - Math.floor(sr)) == 0);
}
// Function that returns true
// if n is a Fibonacci number
function isFibonacci(n)
{
return isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4);
}
// Function to return the count of good cells
function goodCells(mat)
{
// To store the required count
let count = 0;
for (let i = 0; i < M; i++)
{
for (let j = 0; j < N; j++)
{
let sum = mat[i][j];
// Corner cells of the matrix
// have only 2 adjacent cells
if ((i == 0 && j == 0)
|| (i == M - 1 && j == 0)
|| (i == 0 && j == N - 1)
|| (i == M - 1 && j == N - 1))
{
sum += 2;
}
// All the boundary elements
// except the corner elements
// have only 3 adjacent cells
else if (i == 0 || j == 0
|| i == M - 1 || j == N - 1)
{
sum += 3;
}
// Rest of the elements have 4 adjacent cells
else
{
sum += 4;
}
// If the sum is a Fibonacci number
if (isFibonacci(sum))
count++;
}
}
return count;
}
let mat = [ [ 1, 0, 5, 3 ],
[ 2, 17, 5, 6 ],
[ 5, 8, 15, 11 ] ];
document.write( goodCells(mat));
</script>
Producción
7
Complejidad de tiempo: O(N*M)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por SURENDRA_GANGWAR y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA