Description#
You are given a 0-indexed two-dimensional integer array nums
.
Return the largest prime number that lies on at least one of the diagonals of nums
. In case, no prime is present on any of the diagonals, return 0.
Note that:
- An integer is prime if it is greater than
1
and has no positive integer divisors other than 1
and itself. - An integer
val
is on one of the diagonals of nums
if there exists an integer i
for which nums[i][i] = val
or an i
for which nums[i][nums.length - i - 1] = val
.
![](https://spcdn.pages.dev/leetcode/problems/2614.Prime%20In%20Diagonal/images/screenshot-2023-03-06-at-45648-pm.png)
In the above diagram, one diagonal is [1,5,9] and another diagonal is [3,5,7].
Example 1:
Input: nums = [[1,2,3],[5,6,7],[9,10,11]]
Output: 11
Explanation: The numbers 1, 3, 6, 9, and 11 are the only numbers present on at least one of the diagonals. Since 11 is the largest prime, we return 11.
Example 2:
Input: nums = [[1,2,3],[5,17,7],[9,11,10]]
Output: 17
Explanation: The numbers 1, 3, 9, 10, and 17 are all present on at least one of the diagonals. 17 is the largest prime, so we return 17.
Constraints:
1 <= nums.length <= 300
nums.length == numsi.length
1 <= nums[i][j] <= 4*106
Solutions#
Solution 1: Math + Simulation#
We implement a function is_prime
to check whether a number is prime.
Then we iterate the array and check whether the numbers on the diagonals are prime. If so, we update the answer.
The time complexity is $O(n \times \sqrt{M})$, where $n$ and $M$ are the number of rows of the array and the maximum value in the array, respectively. The space complexity is $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def diagonalPrime(self, nums: List[List[int]]) -> int:
def is_prime(x: int) -> bool:
if x < 2:
return False
return all(x % i for i in range(2, int(sqrt(x)) + 1))
n = len(nums)
ans = 0
for i, row in enumerate(nums):
if is_prime(row[i]):
ans = max(ans, row[i])
if is_prime(row[n - i - 1]):
ans = max(ans, row[n - i - 1])
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int diagonalPrime(int[][] nums) {
int n = nums.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
if (isPrime(nums[i][i])) {
ans = Math.max(ans, nums[i][i]);
}
if (isPrime(nums[i][n - i - 1])) {
ans = Math.max(ans, nums[i][n - i - 1]);
}
}
return ans;
}
private boolean isPrime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i <= x / i; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int diagonalPrime(vector<vector<int>>& nums) {
int n = nums.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
if (isPrime(nums[i][i])) {
ans = max(ans, nums[i][i]);
}
if (isPrime(nums[i][n - i - 1])) {
ans = max(ans, nums[i][n - i - 1]);
}
}
return ans;
}
bool isPrime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i <= x / i; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func diagonalPrime(nums [][]int) (ans int) {
n := len(nums)
for i, row := range nums {
if isPrime(row[i]) {
ans = max(ans, row[i])
}
if isPrime(row[n-i-1]) {
ans = max(ans, row[n-i-1])
}
}
return
}
func isPrime(x int) bool {
if x < 2 {
return false
}
for i := 2; i <= x/i; i++ {
if x%i == 0 {
return false
}
}
return true
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| impl Solution {
pub fn diagonal_prime(nums: Vec<Vec<i32>>) -> i32 {
let mut ans = 0;
let n = nums.len();
for (i, row) in nums.iter().enumerate() {
if Self::is_prime(row[i]) && row[i] > ans {
ans = row[i];
}
if Self::is_prime(row[n - i - 1]) && row[n - i - 1] > ans {
ans = row[n - i - 1];
}
}
ans
}
fn is_prime(n: i32) -> bool {
if n < 2 {
return false;
}
let upper = (n as f64).sqrt() as i32;
for i in 2..=upper {
if n % i == 0 {
return false;
}
}
true
}
}
|