Leetcode 3044: Most Frequent Prime
You are given a matrix of integers, where each cell contains a digit from 1 to 9. Starting from any cell in the matrix, you can move in one of eight possible directions (east, south-east, south, south-west, west, north-west, north, and north-east) and create numbers by appending the digits along the path. For each valid path, numbers greater than 10 are generated. The task is to find the most frequent prime number greater than 10 among all the numbers generated by traversing the matrix. If there are multiple such prime numbers, return the largest one. If no prime number exists, return -1.
Problem
Approach
Steps
Complexity
Input: You are given a 2D matrix 'mat' of size m x n, where 1 <= m, n <= 6, and each element in mat is between 1 and 9 (inclusive).
Example: mat = [[2, 3, 4], [5, 6, 7], [8, 9, 1]]
Constraints:
• 1 <= m, n <= 6
• 1 <= mat[i][j] <= 9
Output: Return the most frequent prime number greater than 10 formed by traversing the matrix. If no such prime exists, return -1.
Example: For mat = [[2, 3, 4], [5, 6, 7], [8, 9, 1]], the output is 23.
Constraints:
Goal: Traverse the matrix from each cell, generate numbers by moving in any of the 8 directions, and identify the most frequent prime number greater than 10.
Steps:
• 1. Define directions for traversal (east, south-east, south, etc.).
• 2. For each cell, generate numbers by moving in the defined directions.
• 3. Check if the generated number is a prime number greater than 10.
• 4. Keep track of the frequency of prime numbers.
• 5. Return the most frequent prime number greater than 10. If there are multiple such numbers, return the largest one. If none exists, return -1.
Goal: The constraints are as follows:
Steps:
• Matrix size is at most 6x6.
• The digits in each cell of the matrix are between 1 and 9.
Assumptions:
• You can move in one of eight possible directions from any cell.
• Numbers are formed by traversing through consecutive cells in a chosen direction.
• Input: For the input matrix mat = [[2, 3, 4], [5, 6, 7], [8, 9, 1]]
• Explanation: Start from each cell and move in all 8 possible directions. The numbers greater than 10 are generated. Among these, the prime number 23 appears the most frequently, so the output is 23.
Approach: The problem can be solved by generating all the numbers formed by traversing the matrix in all 8 directions, checking which numbers are prime and greater than 10, and then finding the most frequent prime.
Observations:
• We need to check every direction from each cell and generate numbers.
• Prime numbers can be checked using a sieve of Eratosthenes.
• The number of cells and directions are small, so the problem can be approached using brute force.
Steps:
• 1. Precompute all prime numbers up to a certain limit using a sieve.
• 2. Traverse each cell in the matrix and for each direction generate numbers.
• 3. For each generated number, check if it is prime and greater than 10.
• 4. Use a map to track the frequency of prime numbers.
• 5. Return the most frequent prime number or -1 if no prime numbers are found.
Empty Inputs:
• The matrix will always have at least one element.
Large Inputs:
• The maximum size of the matrix is 6x6.
Special Values:
• If no prime numbers greater than 10 are generated, return -1.
Constraints:
• The matrix elements are between 1 and 9, and the matrix dimensions are at most 6x6.
int dx[8] = {1, 1, 1, -1, -1, -1, 0, 0};
int dy[8] = {1, 0, -1, 1, 0, -1, 1, -1};
void make() {
sieve[1] = 1;
for (int i = 2; i < 1000001; i++) {
if (!sieve[i]) for (int j = 2*i; j < 1000001; j += i) sieve[j] = 1;
}
}
int mostFrequentPrime(vector<vector<int>>& mat) {
if (sieve[1] == 0) make();
map<int, int> freq;
for (int i = 0; i < mat.size(); i++) {
for (int j = 0; j < mat[i].size(); j++) {
for (int k = 0; k < 8; k++) {
int a = i, b = j;
int cur = 0;
while (a >= 0 && b >= 0 && a < mat.size() && b < mat[i].size()) {
cur *= 10;
cur += mat[a][b];
if(cur>10 && sieve[cur] == 0) freq[cur]++;
a += dx[k]; b += dy[k];
}
}
}
}
int mx = -1;
int ans = -1;
for (auto i : freq) {
if(i.second >= mx) {
ans = i.first;
mx = i.second;
}
}
return ans;
}
1 : Variable Initialization
int dx[8] = {1, 1, 1, -1, -1, -1, 0, 0};
Declares an array `dx` to represent the directional movements in the x-axis for the 8 possible directions.
2 : Variable Initialization
int dy[8] = {1, 0, -1, 1, 0, -1, 1, -1};
Declares an array `dy` to represent the directional movements in the y-axis for the 8 possible directions.
3 : Function Definition
void make() {
Defines the `make` function to initialize the sieve array to mark non-prime numbers.
4 : Assignment
sieve[1] = 1;
Marks the number `1` as non-prime in the sieve array.
5 : Loop
for (int i = 2; i < 1000001; i++) {
Starts a loop to iterate through numbers from `2` to `1000000` to apply the sieve of Eratosthenes.
6 : Condition Check
if (!sieve[i]) for (int j = 2*i; j < 1000001; j += i) sieve[j] = 1;
Checks if the current number `i` is prime. If it is, marks all multiples of `i` as non-prime.
7 : Function Definition
int mostFrequentPrime(vector<vector<int>>& mat) {
Defines the `mostFrequentPrime` function, which identifies the most frequent prime formed by traversing an input matrix `mat`.
8 : Condition Check
if (sieve[1] == 0) make();
Checks if the sieve is initialized, and if not, calls the `make` function to initialize it.
9 : Variable Initialization
map<int, int> freq;
Declares a map `freq` to store the frequency of prime numbers found during matrix traversal.
10 : Outer Loop
for (int i = 0; i < mat.size(); i++) {
Starts the outer loop to iterate over each row of the matrix `mat`.
11 : Inner Loop
for (int j = 0; j < mat[i].size(); j++) {
Starts the inner loop to iterate over each element in the current row `mat[i]`.
12 : Direction Loop
for (int k = 0; k < 8; k++) {
Starts a loop to iterate over all 8 possible directions for traversing the matrix.
13 : Variable Initialization
int a = i, b = j;
Initializes the variables `a` and `b` to represent the current position in the matrix.
14 : Variable Initialization
int cur = 0;
Initializes a variable `cur` to 0, which will hold the current number formed by traversing in a specific direction.
15 : While Loop
while (a >= 0 && b >= 0 && a < mat.size() && b < mat[i].size()) {
Starts a `while` loop to traverse the matrix in a specific direction as long as the indices `a` and `b` are within bounds.
16 : Number Construction
cur *= 10;
Multiplies the current number `cur` by 10 to shift its digits and prepare to add the next digit.
17 : Number Construction
cur += mat[a][b];
Adds the current matrix element `mat[a][b]` to the number `cur`.
18 : Prime Check
if(cur > 10 && sieve[cur] == 0) freq[cur]++;
Checks if the number `cur` is greater than 10 and a prime (using the sieve), and increments its frequency in the `freq` map.
19 : Move to Next Cell
a += dx[k]; b += dy[k];
Moves to the next cell in the matrix according to the current direction specified by `dx[k]` and `dy[k]`.
20 : Variable Initialization
int mx = -1;
Initializes a variable `mx` to store the maximum frequency of a prime number.
21 : Variable Initialization
int ans = -1;
Initializes a variable `ans` to store the prime number with the maximum frequency.
22 : Loop
for (auto i : freq) {
Starts a loop to iterate over the frequency map `freq`.
23 : Condition Check
if(i.second >= mx) {
Checks if the current frequency `i.second` is greater than or equal to the maximum frequency `mx`.
24 : Update Variables
ans = i.first;
Updates the variable `ans` to the current prime number with the maximum frequency.
25 : Update Variables
mx = i.second;
Updates the variable `mx` to the current frequency of the prime number.
26 : Return Statement
return ans;
Returns the prime number with the maximum frequency.
Best Case: O(m * n)
Average Case: O(m * n * d)
Worst Case: O(m * n * d)
Description: The time complexity is O(m * n * d), where m and n are the dimensions of the matrix, and d is the number of directions (8 in this case).
Best Case: O(p)
Worst Case: O(p)
Description: The space complexity is O(p), where p is the number of prime numbers greater than 10 found in the matrix.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus