Count of cells in a matrix which give a Fibonacci number when the count of adjacent cells is added
Given an M x N matrix mat[][]. The task is to count the number of good cells in the matrix. A cell will be good if the sum of the cell value and the number of the adjacent cells is a Fibonacci number.
Examples:
Input: mat[][] = {
{1, 2},
{3, 4}}
Output: 2
Only the cells mat[0][0] and mat[1][0] are good.
i.e. (1 + 2) = 3 and (3 + 2) = 5 are both Fibonacci numbers.
Input: mat[][] = {
{1, 0, 5, 3},
{2, 17, 5, 6},
{5, 8, 15, 11}};
Output: 7
Approach: Iterate the entire matrix and for each cell find the count of adjacent cells. There can be 3 types of cells, one with 2 adjacent cells, one with 3 adjacent cells and the rest with 4 adjacent cells. Sum this count with the value at the current cell and check whether the result is a Fibonacci number. If yes then increment the count.
Below is the implementation of the above approach:
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> |
7
Time Complexity: O(N*M)
Auxiliary Space: O(1)