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

Maximum Prime Difference

Number: 3373

Difficulty: Medium

Paid? No

Companies: Unstop

Problem Description

Given an array of integers nums, find the maximum distance (difference in indices) between two prime numbers in the array. If only one prime exists, the answer is 0.

Key Insights

  • Since nums[i] is at most 100, we can precompute the prime numbers up to 100.
  • Iterate over the array and record the indices where the number is prime.
  • The maximum distance is the difference between the last and first indices in the list of prime indices.
  • If there is only one prime index, the maximum difference is 0.

Space and Time Complexity

Time Complexity: O(n) where n is the length of nums, since we iterate over the array once and checking for prime status is O(1) with precomputation. Space Complexity: O(n) in the worst-case scenario for storing indices of prime numbers.

Solution

We first precompute the set (or boolean lookup) of prime numbers from 1 to 100. Then, while scanning through the nums array, we gather the indices that correspond to primes. Finally, we calculate the maximum difference by subtracting the first prime index from the last prime index. This approach is efficient given the constraints, and by using a set for prime lookups, we ensure that each check is done in constant time.

Code Solutions

# Python solution for Maximum Prime Difference

def maximumPrimeDifference(nums):
    # Precompute prime numbers up to 100 using a helper function
    def is_prime(num):
        if num < 2:
            return False
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

    # Create a set of primes for numbers from 1 to 100
    primes_set = {num for num in range(1, 101) if is_prime(num)}

    # List to store indices of prime numbers in nums
    prime_indices = []
    for index, value in enumerate(nums):
        if value in primes_set:
            prime_indices.append(index)

    # Maximum difference between the first and last prime index
    return prime_indices[-1] - prime_indices[0]

# Example usage:
nums1 = [4, 2, 9, 5, 3]
print(maximumPrimeDifference(nums1))  # Expected output: 3
← Back to All Questions