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.
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 <= 300nums.length == numsi.length1 <= 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
}
}
|
