MATFILL - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice

Author: Mann Mehta

Tester: Jaymeet Mehta

Editorialist: Vatsal Parmar

DIFFICULTY

Easy

PREREQUISITES

Basic Math, Modulo Operations, Prime Algorithms, Factorisation, Observation

PROBLEM

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.

EXPLANATION

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.


Solution-2: -


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.

  1. Iterate all the number from 2 to N-1 and check if number divides N or not School Method
  2. 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
  3. 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 COMPLEXITY

Time Complexity is depend on the which method is use to check the number is prime or Not.
  1. Sieve of Eratosthenes O(N) over all test cases. Here (max(N) is 10^5)
  2. Optimize School Method O(√N) per each test case.

    School Method give TLE verdict !!!

SOLUTIONS

Author’s Solution

Tester’s Solution

Editorialist’s Solution