Given integer N denoting the size of a square matrix whose each element is the sum of its row and column i.e., mat[i][j] = i + j (0 < i, j, ≤ N), and an integer X, the task is to find how many cells have the value X.
Examples:
Input: N = 4, X = 2
Output: 1
Explanation: The matrix we get after using M(a, b) = a + b is:
2 3 4 5
3 4 5 6
4 5 6 7
5 6 7 8
At M[1][1] = X There is only value equals to 2.Input: N = 3, X = 4
Output: 3
Explanation: The matrix we get after using M(a, b) = a + b is:
2 3 4
3 4 5
4 5 6
At M[1][3], M[2][2], M[3][1] = X There is 3 Times x appears.Input: N = 1, X = 3
Output: 0
Explanation: The matrix we get after using M(a, b) = a + b is:
The matrix is { 2 }. So no value 3
Naive Approach: The easiest way is to create the Matrix and count the cells have value X.
Below is the implementation of the above approach.
C++
// C++ code of the above approach.#include <bits/stdc++.h>using namespace std;// Function to find the number of times// X is present in the matrixlong long int solve(long long int n, long long int x){ long long int total = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) if (i + j == x) total++; } return total;}// Driver codeint main(){ int N = 4; int X = 2; cout << solve(N, X); return 0;} |
Java
// Java code of the above approach.import java.io.*;class GFG { // Function to find the number of times // X is present in the matrix static long solve(long n, long x) { long total = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) if (i + j == x) total++; } return total; } // Driver code public static void main (String[] args) { int N = 4; int X = 2; System.out.println(solve(N, X)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python3 code of the above approach.# Function to find the number of times# X is present in the matrixdef solve(n, x): total = 0; for i in range(1, n + 1): for j in range(1, n + 1): if (i + j == x): total += 1; return total;# Driver codeif __name__ == '__main__': N = 4; X = 2; print(solve(N, X));# This code is contributed by gauravrajput1 |
C#
// C# code of the above approach.using System;class GFG { // Function to find the number of times // X is present in the matrix static long solve(long n, long x) { long total = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) if (i + j == x) total++; } return total; } // Driver code public static void Main() { int N = 4; int X = 2; Console.WriteLine(solve(N, X)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach// Function to find the number of times// X is present in the matrixfunction solve(n, x){ let total = 0; for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) if (i + j == x) total++; } return total;} // Driver Code let N = 4; let X = 2; document.write(solve(N, X)); // This code is contributed by code_hunt.</script> |
1
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The problem can be efficiently solved using the following mathematical observation:
The numbers across the secondary diagonal (top-right to bottom-left) and parallel to those will be the same.
The value in the secondary diagonal will be (1 + N).
The minimum value in a diagonal will be 2 and maximum will be N+N = 2*N.So there can be two cases:
When X < N+1:
=> It will be on the upper half of the secondary diagonal.
=> X can be formed by [1 + (X-1)], [2 + (X-2)], [3 + (X-3)] + . . . + [(X-1)+1].
=> From the above arrangement it can be seen that the X will be in the cells (1, X-1), (2, X-2), (3, X-3), . . ., (X-1, 1).
=> So total occurrences are is the total number of values in range [1, X-1] = X – 1.When X > N+1:
=> It will be on the lower half of the secondary diagonal.
=> X can be formed by [(X-N) + N], [(X-N+1) + N-1], [(X-N+2) + (N-2)] + . . . + [N + (X-N)].
=> From the above arrangement it can be seen that the X will be in the cells (X-N, N), (X-N+1, N-1), ( X-N+2, N-2), . . ., (N, X-N).
=> So total occurrences are is the total number of values in range [X-N, N] = N – (X – N) + 1 = 2*N – X + 1.(N+1) can be considered in any of the cases and that will give result as N.
Follow the steps mentioned below to implement the above observation:
- Check if X is greater than N+1 or not.
- Then use the formula as derived above.
Below is the implementation of the above approach.
C++
// C++ code for the above approach.#include <bits/stdc++.h>using namespace std;// Function to find// the number of occurrences of Xlong long int solve(long long int N, long long int X){ if (X == 0 || X > 2 * N) return 0; if (X <= N + 1) return X - 1; else return N + N + 1 - X;}// Driver codeint main(){ int N = 4; int X = 2; cout << solve(N, X); return 0;} |
Java
// Java Program of the above approach.import java.util.*;class GFG { // Function to find // the number of occurrences of X static int solve(int N, int X) { if (X == 0 || X > 2 * N) return 0; if (X <= N + 1) return X - 1; else return N + N + 1 - X; } // Driver Code public static void main(String args[]) { int N = 4; int X = 2; System.out.print(solve(N, X)); }}// This code is contributed by code_hunt. |
Python3
# Python code for the above approach# Function to find# the number of occurrences of Xdef solve(N, X) : if (X == 0 or X > 2 * N) : return 0 if (X <= N + 1) : return X - 1 else : return N + N + 1 - X# Driver codeN = 4X = 2print(solve(N, X))# This code is contributed by sanjoy_62. |
C#
// C# Program of the above approach.using System;class GFG { // Function to find // the number of occurrences of X static int solve(int N, int X) { if (X == 0 || X > 2 * N) return 0; if (X <= N + 1) return X - 1; else return N + N + 1 - X; } // Driver Code public static void Main() { int N = 4; int X = 2; Console.Write(solve(N, X)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach. // Function to find // the number of occurrences of X const solve = (N, X) => { if (X == 0 || X > 2 * N) return 0; if (X <= N + 1) return X - 1; else return N + N + 1 - X; } // Driver code let N = 4; let X = 2; document.write(solve(N, X));// This code is contributed by rakeshsahni</script> |
1
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
