Basic Math, Modulo Operations, Prime Algorithms, Factorisation, Observation
You have given an integer N denotes Matrix Mat[N][N], where N \times N should have exactly 3-Factors. Here you also given a integer K, we have to calculate the number of occurrence of integer K in Mat[N][N] where every mat[i][j] element have value (i \times j) modulo N.
Solution-1 (Brute Force Approach): -
Factorize N and count the number of factor’s of N^2. If it count to 3 factor’s then go for next step where you have to construct 2-D mat[N][N], where every mat[i][j] = ((i+1) \times (j+1)) modulo N. Considering index from 0 to N-1.
After that count the number of times that K occur in the Filled Matrix.
Now this is O(N^3) Complexity where Optimization require to get AC.
All prime number’s have exactly 2 factors, but when we are talking about it’s square it have exactly 3 factor's, that are 1, P, P^2. where P is Prime Number.
Now, To check whether the number is prime or not. We have different methods to check.
- Iterate all the number from 2 to N-1 and check if number divides N or not School Method
Iterate all the from 2 to \sqrt N and check if number divide N or not Optimize School Method. Instead of checking till n, we can check till vn because a larger factor of n must be a multiple of smaller factor that has been already checked
- Sieve of Eratosthenes
Now, you have to check the occurrence of K in the filled matrix, here you don’t have to fill the entire Matrix instead you require basic math and observation to reach the optimize solution.
When we observe carefully we will find out that in N × N matrix where N is prime Number, then any number between 1 to N-1 occur’s exactly (N-1) times and 0 occurs exactly 2N − 1 times.
N × N = (N-1) × (N-1) + 2N − 1
N × N = N^2 − 2N + 1 + 2N − 1
N × N = N^2
Here we conclude that matrix contain only number from 0 to N-1.
also A modulo N give value in range (0 to N-1 only)
TIME COMPLEXITYTime Complexity is depend on the which method is use to check the number is prime or Not.
- Sieve of Eratosthenes O(N) over all test cases. Here (max(N) is 10^5)
- Optimize School Method O(√N) per each test case.
School Method give TLE verdict !!!