algoadvance

Leetcode 1175. Prime Arrangements

Problem Statement

Given an integer n, you need to return the number of prime arrangements. You can rearrange the first n positive integers to make nums such that the number of prime numbers present in the first k positions of the rearranged array is equal to k. Since the answer may be large, return it modulo 10^9 + 7.

Clarifying Questions

  1. Range of n: What is the range of the input integer n?
    • 1 <= n <= 100
  2. Prime Definition: Are we following the standard definition of prime numbers (i.e., a prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself)?
    • Yes, we follow the standard definition of prime numbers.
  3. Output Format: Should the output be a single integer representing the number of prime arrangements modulo 10^9 + 7?
    • Yes, the result should be modulo 10^9 + 7.

Strategy

  1. Prime Counting: First, determine how many prime numbers are there up to n. We can use the Sieve of Eratosthenes to count the primes efficiently.
  2. Factorials for Arrangements: Calculate the factorial of the count of primes and the factorial of the count of non-primes.
  3. Permutation Calculation: The number of valid permutations will be the product of these two factorials.

Steps

  1. Sieve of Eratosthenes: To find all prime numbers up to n.
  2. Count Primes: Calculate the total number of primes from the sieve.
  3. Factorial Calculation: Compute the factorial of the number of primes and the factorial of the number of non-primes.
  4. Final Result: Multiply these two factorials and take the result modulo 10^9 + 7.

Code

import java.util.*;

public class PrimeArrangements {
    private static final int MOD = 1_000_000_007;

    public int numPrimeArrangements(int n) {
        int primeCount = countPrimes(n);

        // Calculate factorial of primeCount and nonPrimeCount
        long primeFactorial = factorial(primeCount);
        long nonPrimeFactorial = factorial(n - primeCount);
        
        // Return the product modulo 10^9 + 7
        return (int) ((primeFactorial * nonPrimeFactorial) % MOD);
    }

    private int countPrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false; // 0 and 1 are not primes

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

        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        return count;
    }

    private long factorial(int num) {
        long result = 1;
        for (int i = 2; i <= num; i++) {
            result = (result * i) % MOD;
        }
        return result;
    }

    public static void main(String[] args) {
        PrimeArrangements sol = new PrimeArrangements();
        System.out.println(sol.numPrimeArrangements(5));  // Example output: 12
        System.out.println(sol.numPrimeArrangements(100));  // Example output
    }
}

Time Complexity

This approach ensures that we handle the constraints efficiently and return the result within permissible computational limits.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI