3115. Maximum Prime Difference

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.

Examples

Example 1:

Input: nums = [4,2,9,5,3]

Output: 3

Explanation: nums[1], nums[3], and nums[4] are prime. So the answer is |4 - 1| = 3.

Example 2:

Input: nums = [4,8,2,8]

Output: 0

Explanation: nums[2] is prime. Because there is just one prime number, the answer is |2 - 2| = 0.

 

Constraints

• 1 <= nums.length <= 3 * 10^5
• 1 <= nums[i] <= 100
• The input is generated such that the number of prime numbers in the nums is at least one.

Solution for3115. Maximum Prime Difference

1. Sieve of Eratosthenes

• Use the Sieve of Eratosthenes to generate a list of prime numbers up to the maximum number in the array.

2. Find Prime Indices

• Iterate through the array and record the indices of all prime numbers.

3. Calculate Maximum Difference

• Sort the list of indices and find the difference between the maximum and minimum indices.

Detailed Steps in Code

1. Sieve of Eratosthenes:

   • Initialize a boolean array prime where prime[i] indicates whether i is a prime number.
   • Set all values in prime to true, except for prime[0] and prime[1] which are set to false.
   • For each number p from 2 to the square root of n, mark all multiples of p as false.

2. Find Prime Indices:

   • Iterate through the array nums and store the indices of prime numbers in a list p.

3. Calculate Maximum Difference:

   • Sort the list p of indices.
   • The maximum difference is the difference between the last and first elements in the sorted list p.

Solution

Implementation

Live Editor

function Solution(arr) {
    function SieveOfEratosthenes(n) {
    let prime = Array(n + 1).fill(true);
    prime[0] = prime[1] = false;

    for (let p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (let i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }

    return prime;
}

function maximumPrimeDifference(nums) {
    let maxi = Math.max(...nums);
    let prime = SieveOfEratosthenes(maxi);
    let p = [];

    for (let i = 0; i < nums.length; i++) {
        if (prime[nums[i]]) {
            p.push(i);
        }
    }

    p.sort((a, b) => a - b);

    return p[p.length - 1] - p[0];
}

  const input = [4,2,9,5,3]
  const output = maximumPrimeDifference(input)
  return (
    <div>
      <p>
        <b>Input: </b>
        {JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}

Result

Loading...

Complexity Analysis

• Time Complexity: $O(nlogn)$
• Space Complexity: $O(n)$

Code in Different Languages

JavaScript

Written by @hiteshgahanolia

function SieveOfEratosthenes(n) {
 let prime = Array(n + 1).fill(true);
 prime[0] = prime[1] = false;

 for (let p = 2; p * p <= n; p++) {
     if (prime[p]) {
         for (let i = p * p; i <= n; i += p) {
             prime[i] = false;
         }
     }
 }

 return prime;
}

function maximumPrimeDifference(nums) {
 let maxi = Math.max(...nums);
 let prime = SieveOfEratosthenes(maxi);
 let p = [];

 for (let i = 0; i < nums.length; i++) {
     if (prime[nums[i]]) {
         p.push(i);
     }
 }

 p.sort((a, b) => a - b);

 return p[p.length - 1] - p[0];
}

TypeScript

Written by @hiteshgahanolia

function SieveOfEratosthenes(n: number): boolean[] {
 let prime: boolean[] = Array(n + 1).fill(true);
 prime[0] = prime[1] = false;

 for (let p = 2; p * p <= n; p++) {
     if (prime[p]) {
         for (let i = p * p; i <= n; i += p) {
             prime[i] = false;
         }
     }
 }

 return prime;
}

function maximumPrimeDifference(nums: number[]): number {
 let maxi: number = Math.max(...nums);
 let prime: boolean[] = SieveOfEratosthenes(maxi);
 let p: number[] = [];

 for (let i = 0; i < nums.length; i++) {
     if (prime[nums[i]]) {
         p.push(i);
     }
 }

 p.sort((a, b) => a - b);

 return p[p.length - 1] - p[0];
}

Python

Written by @hiteshgahanolia

class Solution:
 def __init__(self):
     self.prime = [True] * 1000001

 def SieveOfEratosthenes(self, n: int) -> None:
     self.prime[0] = self.prime[1] = False

     for p in range(2, int(n**0.5) + 1):
         if self.prime[p]:
             for i in range(p * p, n + 1, p):
                 self.prime[i] = False

 def maximumPrimeDifference(self, nums: List[int]) -> int:
     maxi = max(nums)
     self.SieveOfEratosthenes(maxi)
     p = []

     for i in range(len(nums)):
         if self.prime[nums[i]]:
             p.append(i)

     p.sort()

     return p[-1] - p[0]

Java

Written by @hiteshgahanolia

import java.util.*;

class Solution {
 boolean[] prime = new boolean[1000001];

 void SieveOfEratosthenes(int n) {
     Arrays.fill(prime, true);
     prime[0] = prime[1] = false;

     for (int p = 2; p * p <= n; p++) {
         if (prime[p]) {
             for (int i = p * p; i <= n; i += p) {
                 prime[i] = false;
             }
         }
     }
 }

 public int maximumPrimeDifference(int[] nums) {
     int maxi = Arrays.stream(nums).max().orElse(0);
     SieveOfEratosthenes(maxi);
     List<Integer> p = new ArrayList<>();

     for (int i = 0; i < nums.length; i++) {
         if (prime[nums[i]]) {
             p.add(i);
         }
     }

     Collections.sort(p);

     return p.get(p.size() - 1) - p.get(0);
 }
}

C++

Written by @hiteshgahanolia

class Solution {
public:
 bool prime[1000001]; 
 void SieveOfEratosthenes(int n) {
     memset(prime, true, sizeof(prime));
     prime[0] = prime[1] = false; 
     for (int p = 2; p * p <= n; p++) {
         if (prime[p] == true) {
             for (int i = p * p; i <= n; i += p)
                 prime[i] = false;
         }
     }
 }
 int maximumPrimeDifference(vector<int>& nums) {
     int maxi = *max_element(nums.begin(), nums.end());
     SieveOfEratosthenes(maxi);
     vector<int> p;
     for (int i = 0; i < nums.size(); i++) {
         if (prime[nums[i]]) { 
             p.push_back(i);
         }
     }
     sort(p.begin(), p.end());
     return p[p.size() - 1] - p[0];
 }
};

References

• LeetCode Problem: 2348. Number of Zero-Filled Subarrays

• Solution Link: LeetCode Solution