Posts tagged as “prime”

花花酱 LeetCode 1998. GCD Sort of an Array

By zxi on December 31, 2021

You are given an integer array nums, and you can perform the following operation any number of times on nums:

Swap the positions of two elements nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j].

Return true if it is possible to sort nums in non-decreasing order using the above swap method, or false otherwise.

Example 1:

Input: nums = [7,21,3]
Output: true
Explanation: We can sort [7,21,3] by performing the following operations:
- Swap 7 and 21 because gcd(7,21) = 7. nums = [21,7,3]
- Swap 21 and 3 because gcd(21,3) = 3. nums = [3,7,21]

Example 2:

Input: nums = [5,2,6,2]
Output: false
Explanation: It is impossible to sort the array because 5 cannot be swapped with any other element.

Example 3:

Input: nums = [10,5,9,3,15]
Output: true
We can sort [10,5,9,3,15] by performing the following operations:
- Swap 10 and 15 because gcd(10,15) = 5. nums = [15,5,9,3,10]
- Swap 15 and 3 because gcd(15,3) = 3. nums = [3,5,9,15,10]
- Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,10,15]

Constraints:

1 <= nums.length <= 3 * 10⁴
2 <= nums[i] <= 10⁵

Solution: Union-Find

Let nums[j]’s target position be i. In order to put nums[j] to pos i by swapping. nums[i] and nums[j] must be in the same connected component. There is an edge between two numbers if they have gcd > 1.

We union two numbers if their have gcd > 1. However, it will be TLE if we do all pairs . Thus, for each number, we union it with its divisors instead.

Time complexity: O(n²) TLE -> O(sum(sqrt(nums[i]))) <= O(n*sqrt(m))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool gcdSort(vector<int>& nums) {

const int m = *max_element(begin(nums), end(nums));

const int n = nums.size();

vector<int> p(m + 1);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return p[x] == x ? x : (p[x] = find(p[x]));

};

for (int x : nums)

for (int d = 2; d <= sqrt(x); ++d)

if (x % d == 0)

p[find(x)] = p[find(x / d)] = find(d);

vector<int> sorted(nums);

sort(begin(sorted), end(sorted));

for (int i = 0; i < n; ++i)

if (find(sorted[i]) != find(nums[i]))

return false;

return true;

}

};

花花酱 LeetCode 1808. Maximize Number of Nice Divisors

By zxi on March 27, 2021

You are given a positive integer primeFactors. You are asked to construct a positive integer n that satisfies the following conditions:

The number of prime factors of n (not necessarily distinct) is at most primeFactors.
The number of nice divisors of n is maximized. Note that a divisor of n is nice if it is divisible by every prime factor of n. For example, if n = 12, then its prime factors are [2,2,3], then 6 and 12 are nice divisors, while 3 and 4 are not.

Return the number of nice divisors of n. Since that number can be too large, return it modulo 10⁹ + 7.

Note that a prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. The prime factors of a number n is a list of prime numbers such that their product equals n.

Example 1:

Input: primeFactors = 5
Output: 6
Explanation: 200 is a valid value of n.
It has 5 prime factors: [2,2,2,5,5], and it has 6 nice divisors: [10,20,40,50,100,200].
There is not other value of n that has at most 5 prime factors and more nice divisors.

Example 2:

Input: primeFactors = 8
Output: 18

Constraints:

1 <= primeFactors <= 10⁹

Solution: Math

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxNiceDivisors(int n) {

constexpr int kMod = 1e9 + 7;

auto powm = [](long base, int exp) {

long ans = 1;

while (exp) {

if (exp & 1) ans = (ans * base) % kMod;

base = (base * base) % kMod;

exp >>= 1;

}

return ans;

};

if (n <= 3) return n;

switch (n % 3) {

case 0: return powm(3, n / 3);

case 1: return (powm(3, n / 3 - 1) * 4) % kMod;

case 2: return (powm(3, n / 3) * 2) % kMod;

}

return -1;

}

};

花花酱 LeetCode 1735. Count Ways to Make Array With Product

By zxi on January 23, 2021

You are given a 2D integer array, queries. For each queries[i], where queries[i] = [n_i, k_i], find the number of different ways you can place positive integers into an array of size n_i such that the product of the integers is k_i. As the number of ways may be too large, the answer to the i^th query is the number of ways modulo 10⁹ + 7.

Return an integer array answer where answer.length == queries.length, and answer[i] is the answer to the i^th query.

Example 1:

Input: queries = [[2,6],[5,1],[73,660]]
Output: [4,1,50734910]
Explanation: Each query is independent.
[2,6]: There are 4 ways to fill an array of size 2 that multiply to 6: [1,6], [2,3], [3,2], [6,1].
[5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1].
[73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 10⁹ + 7 = 50734910.

Example 2:

Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: [1,2,3,10,5]

Constraints:

1 <= queries.length <= 10⁴
1 <= n_i, k_i <= 10⁴

Solution1: DP

let dp(n, k) be the ways to have product k of array size n.
dp(n, k) = sum(dp(n – 1, i)) where i is a factor of k and i != k.
base case:
dp(0, 1) = 1, dp(0, *) = 0
dp(i, 1) = C(n, i)
e.g.
dp(2, 6) = dp(1, 1) + dp(1, 2) + dp(1, 3)
= 2 + 1 + 1 = 4
dp(4, 4) = dp(3, 1) + dp(3, 2)
= dp(3, 1) + dp(2, 1)
= 4 + 6 = 10

Time complexity: O(sum(k_i))?
Space complexity: O(sum(k_i))?

C++

// Author: Huahua

class Solution {

public:

vector<int> waysToFillArray(vector<vector<int>>& queries) {

constexpr int kMod = 1e9 + 7;

int n = 0;

unordered_map<int, int> c, dp;

function<int(int, int)> cnk = [&](int n, int k) {

if (k > n) return 0;

if (k == 0 || k == n) return 1;

int& ans = c[(n << 16) | k];

if (!ans) ans = (cnk(n - 1, k - 1) + cnk(n - 1, k)) % kMod;

return ans;

};

function<int(int, int)> dfs = [&](int s, int k) -> int {

if (s == 0) return k == 1;

if (k == 1) return cnk(n, s);

int& ans = dp[(s << 16) | k];

if (ans) return ans;

for (int i = 1; i * i <= k; ++i) {

if (k % i) continue;

if (i != 1)

ans = (ans + dfs(s - 1, k / i)) % kMod;

if (i * i != k)

ans = (ans + dfs(s - 1, i)) % kMod;

}

return ans;

};

vector<int> ans;

for (const auto& q : queries) {

dp.clear();

n = q[0];

ans.push_back(dfs(n, q[1]));

}

return ans;

}

};

花花酱 LeetCode 1175. Prime Arrangements

By zxi on August 31, 2019

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:

Input: n = 100
Output: 682289015

Constraints:

1 <= n <= 100

Solution: Permutation

Count the number of primes in range [1, n], assuming there are p primes and n – p non-primes, we can permute each group separately.
ans = p! * (n – p)!

Time complexity: O(nsqrt(n))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numPrimeArrangements(int n) {

const int kMod = 1e9 + 7;

int p = 0;

for (int i = 1; i <= n; ++i)

p += isPrime(i);

long ans = 1;

for (int i = 1; i <= p; ++i)

ans = (ans * i) % kMod;

for (int i = 1; i <= n - p; ++i)

ans = (ans * i) % kMod;

return ans;

}

private:

bool isPrime(int x) {

if (x < 2) return false;

if (x == 2) return true;

for (int i = 2; i <= sqrt(x); ++i)

if (x % i == 0) return false;

return true;

}

};

花花酱 LeetCode 313. Super Ugly Number

By zxi on January 2, 2019

Write a program to find the n^th super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

Example:

Input: n = 12, primes = [2,7,13,19] 
Output: 32  
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12               super ugly numbers given primes = [2,7,13,19] of size 4.

Note:

1 is a super ugly number for any given primes.
The given numbers in primes are in ascending order.
0 < k ≤ 100, 0 < n ≤ 10⁶, 0 < primes[i] < 1000.
The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

Solution 1: Set

Maintain an ordered set of super ugly numbers, each time extract the smallest one, and multiply it with all primes and insert the new number into set.

Time complexity: O(n*k*logn)
Space complexity: O(n)

C++

// Author: Huahua, running time: 484 ms

class Solution {

public:

int nthSuperUglyNumber(int n, vector<int>& primes) {

if (n == 1) return 1;

set<int> q{begin(primes), end(primes)};

for (int i = 0; i < n - 2; ++i) {

auto it = begin(q);

int t = *it;

q.erase(it);

for (int p : primes) {

if (INT_MAX / t < p) continue;

q.insert(p * t);

}

return *begin(q);

}

};

Solution 2: Priority Queue

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua, 40 ms

struct Node {

int num;

int index;

int prime;

bool operator>(const Node& o) const {

if (this->num == o.num) return this->index > o.index;

return this->num > o.num;

}

};

class Solution {

public:

int nthSuperUglyNumber(int n, vector<int>& primes) {

if (n == 1) return 1;

vector<int> nums(n, 1);

priority_queue<Node, vector<Node>, greater<Node>> q;

for (int p : primes)

q.push({p, 1, p});

for (int i = 1; i < n; ++i) {

nums[i] = q.top().num;

while (nums[i] == q.top().num) {

Node node = std::move(q.top()); q.pop();

node.num = nums[node.index++] * node.prime;

q.push(std::move(node));

}

return nums.back();

}

};