LeetCode 1175: Prime Arrangements Solution

Master LeetCode problem 1175 (Prime Arrangements), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1175. Prime Arrangements

Easy

Math

Problem Explanation

Explanation

To solve this problem, we need to count the number of permutations of numbers from 1 to n such that prime numbers occur at prime positions. We can achieve this by calculating the factorial of the count of prime numbers (let's call it primeCount) and the count of non-prime numbers (let's call it nonPrimeCount). The total number of valid permutations will be the product of the factorials of primeCount and nonPrimeCount.

Calculate the count of prime numbers and non-prime numbers in the range 1 to n.
Calculate the factorial of primeCount and nonPrimeCount.
Return the product of the two factorials modulo 10^9 + 7.

Time complexity: O(n * sqrt(n))
Space complexity: O(1)

Solution Code

class Solution {
    public int numPrimeArrangements(int n) {
        int primeCount = countPrimes(n);
        int nonPrimeCount = n - primeCount;
        
        long primeFactorial = factorial(primeCount);
        long nonPrimeFactorial = factorial(nonPrimeCount);
        
        return (int) ((primeFactorial * nonPrimeFactorial) % 1000000007);
    }
    
    private int countPrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        int count = 0;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        for (boolean prime : isPrime) {
            if (prime) {
                count++;
            }
        }
        
        return count;
    }
    
    private long factorial(int n) {
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result = (result * i) % 1000000007;
        }
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1175 (Prime Arrangements)?

This page provides optimized solutions for LeetCode problem 1175 (Prime Arrangements) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1175 (Prime Arrangements)?

The time complexity for LeetCode 1175 (Prime Arrangements) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1175 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1175 in Java, C++, or Python.

Back to LeetCode Solutions