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

Most Frequent Prime

Number: 3314

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a m x n matrix of digits, form numbers by moving in any one of eight fixed directions (without changing direction) starting from any cell. At every step of the path (each digit appended), a new number is formed. Among those numbers that are greater than 10, find all prime numbers, count their frequencies, and return the most frequent prime. In case of frequency ties, return the largest prime. If no such prime exists, return -1.

Key Insights

  • Use eight fixed directions (east, south-east, south, south-west, west, north-west, north, north-east) for path traversal.
  • Generate numbers step-by-step along each path; check numbers as soon as they exceed 10.
  • A helper function is needed to verify if a number is prime.
  • Maintain a frequency dictionary (hash table) to count how many times each prime appears.
  • After processing all cells and directions, select the prime with the highest frequency (and largest value in case of ties).

Space and Time Complexity

Time Complexity: O(m * n * L * sqrt(V)) where L is the maximum length of a path (bounded by grid dimensions) and V is the value of the formed number (with prime checking up to sqrt(V)). Space Complexity: O(P) where P is the number of primes found, stored in a dictionary. Given the tight grid constraints, this is acceptable.

Solution

To solve the problem:

  1. Iterate over each cell in the matrix.
  2. For each cell, explore all 8 directions.
  3. For each direction, build the number step-by-step by iterating until the next cell is out-of-bound.
  4. Once a new digit is added forming a number greater than 10, check if it’s prime. If so, record its frequency in a dictionary.
  5. After processing all paths, inspect the dictionary to find the prime with the highest frequency. If there's a tie, choose the largest prime among them.
  6. Return the identified prime. If no prime number greater than 10 was found, return -1.

Code Solutions

# Python solution with detailed comments

def is_prime(num):
    # Check if a number is prime
    if num < 2:
        return False
    # Only need to check up to sqrt(num)
    i = 2
    while i * i <= num:
        if num % i == 0:
            return False
        i += 1
    return True

def mostFrequentPrime(mat):
    m = len(mat)       # number of rows
    n = len(mat[0])    # number of columns
    prime_freq = {}    # dictionary to store frequency of prime numbers

    # Define the eight directions as (dx, dy)
    directions = [(0, 1), (1, 1), (1, 0), (1, -1),
                  (0, -1), (-1, -1), (-1, 0), (-1, 1)]
    
    # Iterate over every cell in the matrix
    for i in range(m):
        for j in range(n):
            # Explore each of the eight directions
            for dx, dy in directions:
                number = 0
                x, y = i, j
                # Traverse in the current direction until out-of-bound
                while 0 <= x < m and 0 <= y < n:
                    # Append the digit to the current number
                    number = number * 10 + mat[x][y]
                    # Check if the formed number is greater than 10
                    if number > 10:
                        # Check if it is a prime
                        if is_prime(number):
                            # Increase the frequency count for this prime
                            prime_freq[number] = prime_freq.get(number, 0) + 1
                    # Move to the next cell in this direction
                    x += dx
                    y += dy
    
    # If no prime > 10 was found, return -1
    if not prime_freq:
        return -1

    # Determine the prime with highest frequency, or largest prime in case of tie
    max_freq = -1
    candidate = -1
    for prime, freq in prime_freq.items():
        if freq > max_freq or (freq == max_freq and prime > candidate):
            max_freq = freq
            candidate = prime
    
    return candidate

# Example usage:
mat1 = [[1,1],[9,9],[1,1]]
print(mostFrequentPrime(mat1))  # Expected output: 19
← Back to All Questions