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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Prime Difference

Difficulty: Medium

Problem Description

You are given an integer array nums. Return an integer that is the maximum distance between the indices of two (not necessarily different) prime numbers in nums.

Key Insights

  • A prime number is defined as a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
  • The maximum distance can be found by identifying the first and last occurrences of prime numbers in the array.
  • The constraints guarantee that there is at least one prime number in the input.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array nums, since we traverse the array once. Space Complexity: O(1), as we are using a constant amount of extra space for tracking indices.

Solution

To solve the problem, we will:

  1. Iterate through the array while checking each number for primality.
  2. Keep track of the first and last indices where a prime number is found.
  3. Calculate the maximum distance between these two indices.
  4. Return the computed maximum distance.

The algorithm relies on a simple primality test for numbers in the range from 1 to 100, which can be efficiently checked.

Code Solutions

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def max_prime_distance(nums):
    first_index = -1
    last_index = -1
    
    for i, num in enumerate(nums):
        if is_prime(num):
            if first_index == -1:
                first_index = i  # Store the first index of a prime
            last_index = i  # Update the last index of a prime
    
    return last_index - first_index  # Maximum distance

# Example usage
print(max_prime_distance([4, 2, 9, 5, 3]))  # Output: 3
← Back to All Questions