Question

2614. Prime In Diagonal

中文文档

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 <= 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)$.

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

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;
  }
}

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;
  }
};

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
}

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
  }
}