We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Prime In Diagonal

Number: 2722

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a square matrix of integers, the task is to find and return the largest prime number that appears on either of the two diagonals of the matrix. If no prime exists on the diagonals, return 0.

Key Insights

  • Only elements on the main diagonal (nums[i][i]) and the secondary diagonal (nums[i][n-i-1]) are considered.
  • Use a set (or equivalent) to avoid duplicate diagonal elements especially for matrices with an odd dimension.
  • A helper function is essential to check if a given number is prime.
  • Iterate through the candidate numbers, check for prime property, and keep track of the maximum prime found.

Space and Time Complexity

Time Complexity: O(n * sqrt(m)), where n is the dimension of the matrix and m is the value of the number (up to 4*10^6) checked for primality. Space Complexity: O(n) for storing the set of diagonal numbers.

Solution

We first extract all unique elements from both diagonals of the matrix. A set is used to ensure that even if an element appears in both diagonals (like the center element in an odd-sized matrix), it is processed only once. Then for each element in the set, we use a helper function to check if it is prime. In the prime check, we verify that the number is greater than 1 and test for factors up to the square root of the number. Finally, the maximum prime found among the diagonal candidates is returned; if no prime number is found, we return 0.

Code Solutions

# Function to check if a number is prime
def is_prime(num):
    # A number is not prime if it is less than or equal to 1
    if num <= 1:
        return False
    # Check for factors up to the square root of num
    i = 2
    while i * i <= num:
        if num % i == 0:
            return False
        i += 1
    return True

def largest_prime_in_diagonal(nums):
    n = len(nums)
    # Set to store unique elements from both diagonals
    diagonal_elements = set()
    for i in range(n):
        # Add element from the main diagonal
        diagonal_elements.add(nums[i][i])
        # Add element from the anti-diagonal
        diagonal_elements.add(nums[i][n - i - 1])
    
    max_prime = 0
    # Check each candidate for primality and track the maximum
    for num in diagonal_elements:
        if is_prime(num):
            max_prime = max(max_prime, num)
    return max_prime

# Example usage:
# nums = [[1,2,3],[5,6,7],[9,10,11]]
# print(largest_prime_in_diagonal(nums))
← Back to All Questions