algoadvance

Leetcode 1175. Prime Arrangements

Problem Statement

Given an integer n, return the number of prime arrangements. Since the answer may be large, return the answer modulo 10^9 + 7.

A prime arrangement is an arrangement of the integers 1 to n such that:

• The prime numbers are at prime indices (1-indexed).
• The non-prime numbers are at non-prime indices (1-indexed).

Clarifying Questions

1. Input Constraints:
   • Values of n will be in the range 1 to 100.
2. Output:
   • Return an integer representing the number of prime arrangements modulo 10^9 + 7.
3. Prime Numbers:
   • Understanding whether 1 is considered a prime number (it is not).
   • Indices start from 1 when counting prime positions.

Strategy

1. Identifying Prime Numbers:
   • Use the Sieve of Eratosthenes to find all prime numbers up to n.
2. Counting Primes and Non-Primes:
   • Count the number of prime numbers up to n.
   • The number of non-prime numbers can be derived from the total count.
3. Permutations Calculation:
   • Calculate the number of ways to permute the prime numbers among the prime indices (P!).
   • Calculate the number of ways to permute the non-prime numbers among the non-prime indices (N!).
4. Modulo Operation:
   • Since the number can be very large, perform calculations modulo 10^9 + 7.

Code

#include <iostream>
#include <vector>
#include <algorithm>

const int MOD = 1'000'000'007;

int countPrimes(int n) {
    if (n < 2) return 0;
    std::vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return std::count(isPrime.begin(), isPrime.end(), true);
}

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

int numPrimeArrangements(int n) {
    int primeCount = countPrimes(n);
    int nonPrimeCount = n - primeCount;

    long long primeFactorial = factorial(primeCount);
    long long nonPrimeFactorial = factorial(nonPrimeCount);

    return (primeFactorial * nonPrimeFactorial) % MOD;
}

int main() {
    int n;
    std::cin >> n;
    std::cout << numPrimeArrangements(n) << std::endl;
    return 0;
}

Time Complexity

• Sieve of Eratosthenes: (O(n \log \log n)) for counting primes.
• Factorial Calculation: (O(n)).
• Overall: The primary operations are linear or near-linear, resulting in a time complexity of (O(n \log \log n)).

This complexity is efficient given the constraint that n is at most 100.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?