Count occurrences of an element in a matrix of size N * N generated such that each element is equal to product of its indices | Set-2
-Given two positive integers N and X, the task is to count the occurrences of the given integer X in an N-length square matrix generated such that each element of the matrix is equal to the product of its row and column indices (1-based indexing).
Examples:
Input: N = 5, X = 6
Output: 2
Explanation:
The 2D array formed is equal to the :
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25
There are 2 occurrences of the element X(= 6) in the generated array.Input: N = 7, X = 12
Output: 4
Naive Approach: Refer to this article for the simplest approach to solve the problem by constructing the given matrix by multiplying the row and column indices to obtain each matrix element and count the number of occurrences of X.
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient Approach: The idea is based on the observation that the ith row contains all the multiples of i in the range [1, N]. Therefore, X occurs in the ith row if and only if X is exactly divisible by i and X / i should be less than or equal to N. If found to be true, increment the count by 1. Follow the steps below to solve the problem:
- Initialize a variable, say count, to store the count of occurrences of X in the generated matrix.
- Iterate over the range [1, N] using the variable i and perform the following steps:
- If X is divisible by i, store the quotient of X / i in a variable, say b.
- If the value of b falls in the range [1, N], then increase the count by 1.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the occurrences // of X in the generated square matrix int countOccurrences( int n, int x) { // Store the required result int count = 0; // Iterate over the range [1, N] for ( int i = 1; i <= n; i++) { // Check if x is a // multiple of i or not if (x % i == 0) { // Check if the other multiple // exists in the range or not if (x / i <= n) count++; } } // Print the result cout << count; } // Driver Code int main() { int N = 7, X = 12; countOccurrences(N, X); return 0; } |
Java
// Java program for the above approach class GFG{ // Function to count the occurrences // of X in the generated square matrix static void countOccurrences( int n, int x) { // Store the required result int count = 0 ; // Iterate over the range [1, N] for ( int i = 1 ; i <= n; i++) { // Check if x is a // multiple of i or not if (x % i == 0 ) { // Check if the other multiple // exists in the range or not if (x / i <= n) count++; } } // Print the result System.out.print(count); } // Driver Code public static void main(String[] args) { int N = 7 , X = 12 ; countOccurrences(N, X); } } // This code contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # Function to count the occurrences # of X in the generated square matrix def countOccurrences(n, x): # Store the required result count = 0 # Iterate over the range [1, N] for i in range ( 1 , n + 1 ): # Check if x is a # multiple of i or not if (x % i = = 0 ): # Check if the other multiple # exists in the range or not if (x / / i < = n): count + = 1 # Print the result print (count) # Driver Code if __name__ = = "__main__" : N = 7 X = 12 countOccurrences(N, X) # This code is contributed by ukasp |
C#
// C# program for the above approach using System; class GFG { // Function to count the occurrences // of X in the generated square matrix static void countOccurrences( int n, int x) { // Store the required result int count = 0; // Iterate over the range [1, N] for ( int i = 1; i <= n; i++) { // Check if x is a // multiple of i or not if (x % i == 0) { // Check if the other multiple // exists in the range or not if (x / i <= n) count++; } } // Print the result Console.WriteLine(count); } // Driver Code public static void Main(String[] args) { int N = 7, X = 12; countOccurrences(N, X); } } // This code is contributed by splevel62. |
Javascript
<script> // Javascript program for the above approach // Function to count the occurrences // of X in the generated square matrix function countOccurrences(n, x) { // Store the required result var count = 0; // Iterate over the range [1, N] for ( var i = 1; i <= n; i++) { // Check if x is a // multiple of i or not if (x % i == 0) { // Check if the other multiple // exists in the range or not if (x / i <= n) count++; } } // Print the result document.write( count); } // Driver Code var N = 7, X = 12; countOccurrences(N, X); </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)