Sample Examples
Example 1:
Input
n = 5, k = 6
Output
5
Explanation
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
6 7 8 9 10
will be the matrix.
where M(i, j) = i+j in the provided matrix
The recurrence of 7 is FIVE.
Example 2:
Input
n = 3, k = 2
Output
3
Explanation
2 3 4
3 4 5
4 5 6
will be the matrix.
The frequency of 2 is 1 in the given matrix where M(i, j) = i+j.
Approach
- Enter the size of a n x n matrix and an integer value 'k' to search for in a matrix.
- Start loop I from 0 and work your way up to the row size.
- Begin a new loop j within the loop, counting from 0 to column size.
- Make matrix[i][j] equal to i+j.
- Examine matrix[i][j] to see if it equals k.
- Add one to the count if it's a yes; otherwise, return.
- Then the count will be returned
- Print the output
Algorithm
- Make a matrix of size n*n.
- Substitute M(i, j)=i+j for the value.
(Remember that the base index here is 1)
- Iterate through the matrix, counting the frequency of each element.
This method is inefficient because if the matrix size is really high, the time restriction will be surpassed. O(n2) will be the time complexity.
Implementation
C++ Code:
/* C++ program to count frequency of k in a matrix of size n where matrix(i, j) = i+j*/
#include <bits/stdc++.h>
#define ll long long
#define vll vector<long long int>
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define endl "\n"
#define vpi vector<pair<ll,ll>>
#define fi first
#define se second
#define pqi priority_queue<ll,vll,greater<ll>>
#define all(x) x.begin(),x.end()
#define py cout << "YES\n"
#define pn cout << "NO\n"
using namespace std;
int count(ll n, ll k)
{
if (n + 1 >= k)
return (k - 1);
else
return (2 * n + 1 - k);
}
// main Code
int main()
{
ll n = 3, k = 5;
ll cnt = count(n, k);
if (cnt < 0)
cout << " element not exist \n ";
else
cout << " Frequency of " << k
<< " is " << cnt << "\n";
return 0;
}
Output
Time Complexity
As the solution takes a single path from the bottom-left corner to the top or right edge of the matrix, the time complexity is O(1).
Space Complexity
The program's auxiliary space is O(1) because no additional data structure is involved.
Frequently Asked Questions
How do you find the frequency matrix?
Create a matrix of size n*n.
M(i, j)=i+j should be used to fill the value.
(Remember that the base index here is 1)
Iterate through the matrix, counting the frequency of each element.
What is the frequency count method in the algorithm?
We first identify the number of steps per execution (s/e) of each statement and the total number of times each statement is run to calculate the total number of times (i.e. frequency) each statement is run and the number of steps per execution (s/e) of each statement. When these two figures are combined together, the result is, that we get the overall contribution of each statement to the total number of steps.
What does frequency count mean?
The tally, also known as a frequency count, is a calculation that determines how many people fall into a particular group or the number of times a particular feature happens. The absolute (actual number) and relative (%) totals are used in this calculation.
Conclusion
In this blog, we have extensively discussed the Problem to Count the number of times k appears in a matrix of size n, with matrix(i, j) = i+j and its time and space complexities. We hope that this article has helped all of you with additional information about the Data Structures and algorithms. And to learn in-depth about Multi-dimensional Arrays, check out the course on our Arrays on the Coding Ninjas website. Also, take a look at the Coding Ninjas website for some great information, Android Development, Coding Ninjas Studio Problems, Coding Ninjas Studio Interview Bundle, Coding Ninjas Studio Interview Experiences, Coding Ninjas Courses, Coding Ninjas Studio Contests, and Coding Ninjas Studio Test Series. Do upvote our blog in helping other ninjas grow.
Recommended Readings:
Delighted Programming!
38+ registered 