Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Sample Examples
3.1.
Example 1:
3.2.
Input
3.3.
Output
3.4.
Explanation
3.5.
Example 2:
3.6.
Input
3.7.
Output
3.8.
Explanation
4.
Approach
5.
Algorithm
6.
Implementation
6.1.
Output
7.
Time Complexity
7.1.
Space Complexity
8.
Frequently Asked Questions
8.1.
How do you find the frequency matrix?
8.2.
What is the frequency count method in the algorithm?
8.3.
What does frequency count mean?
9.
Conclusion
Last Updated: Mar 27, 2024

Count the number of times k appears in a matrix of size n, with matrix(i, j) = i+j.

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will learn to solve a multidimensional array 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. This blog covers a matrix problem. Matrices are one of the most important and often asked data structures in programming contests and technical interviews. There are various standard matrix problems and techniques.

We will go over the entire problem statement, example application, algorithm and complexities in the following article.

Recommended Topic, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

The aim is to calculate the count of the frequency of a certain integer variable, say, k in the matrix, given a matrix of integer values. The size of a matrix is determined by the user, and in the programme below, we assume it to be n x n. The matrix will be created according to the specified condition, i.e. matrix(i, j) = i+j. The first data in a matrix will have an index value of 0 and 0, i.e. matrix[0][0] = 0.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 DevelopmentCoding Ninjas Studio ProblemsCoding Ninjas Studio Interview BundleCoding Ninjas Studio Interview ExperiencesCoding Ninjas CoursesCoding Ninjas Studio Contests, and Coding Ninjas Studio Test Series. Do upvote our blog in helping other ninjas grow.

Recommended Readings:

Delighted Programming!

Previous article
Minimum Operations required to make each Column and Row of the Matrix Equals
Next article
Sum of the middle row and column in Matrix
Live masterclass