Posts tagged as “factor”

花花酱 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 1627. Graph Connectivity With Threshold

By zxi on October 18, 2020

We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true:

x % z == 0,
y % z == 0, and
z > threshold.

Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [a_i, b_i] if cities a_i and b_i are connected (i.e. there is some path between them).

Return an array answer, where answer.length == queries.length and answer[i] is true if for the i^th query, there is a path between a_i and b_i, or answer[i] is false if there is no path.

Example 1:

Input: n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
Output: [false,false,true]
Explanation: The divisors for each number:
1:   1
2:   1, 2
3:   1, 3
4:   1, 2, 4
5:   1, 5
6:   1, 2, 3, 6
Using the underlined divisors above the threshold, only cities 3 and 6 share a common divisor, so they are the
only ones directly connected. The result of each query:
[1,4]   1 is not connected to 4
[2,5]   2 is not connected to 5
[3,6]   3 is connected to 6 through path 3--6

Example 2:

Input: n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
Output: [true,true,true,true,true]
Explanation: The divisors for each number are the same as the previous example. However, since the threshold is 0,
all divisors can be used. Since all numbers share 1 as a divisor, all cities are connected.

Example 3:

Input: n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]
Output: [false,false,false,false,false]
Explanation: Only cities 2 and 4 share a common divisor 2 which is strictly greater than the threshold 1, so they are the only ones directly connected.
Please notice that there can be multiple queries for the same pair of nodes [x, y], and that the query [x, y] is equivalent to the query [y, x].

Constraints:

2 <= n <= 10⁴
0 <= threshold <= n
1 <= queries.length <= 10⁵
queries[i].length == 2
1 <= a_i, b_i <= cities
a_i != b_i

Solution: Union Find

For x, merge 2x, 3x, 4x, ..,
If a number is already “merged”, skip it.

Time complexity: O(nlogn? + queries)?
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {

if (threshold == 0) return vector<bool>(queries.size(), true);

vector<int> ds(n + 1);

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

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

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

};

for (int x = threshold + 1; x <= n; ++x)

if (ds[x] == x)

for (int y = 2 * x; y <= n; y += x)

ds[max(find(x), find(y))] = min(find(x), find(y));

vector<bool> ans;

for (const vector<int>& q : queries)

ans.push_back(find(q[0]) == find(q[1]));

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def areConnected(self, n: int, threshold: int,

queries: List[List[int]]) -> List[bool]:

if threshold == 0: return [True] * len(queries)

ds = list(range(n + 1))

def find(x: int) -> int:

if x != ds[x]: ds[x] = find(ds[x])

return ds[x]

for x in range(threshold + 1, n + 1):

if ds[x] == x:

for y in range(2 * x, n + 1, x):

ds[max(find(x), find(y))] = min(find(x), find(y))

return [find(x) == find(y) for x, y in queries]

花花酱 LeetCode 1492. The kth Factor of n

By zxi on June 27, 2020

Given two positive integers n and k.

A factor of an integer n is defined as an integer i where n % i == 0.

Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.

Example 1:

Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Example 2:

Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.

Example 3:

Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.

Example 4:

Input: n = 1, k = 1
Output: 1
Explanation: Factors list is [1], the 1st factor is 1.

Example 5:

Input: n = 1000, k = 3
Output: 4
Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000].

Constraints:

1 <= k <= n <= 1000

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int kthFactor(int n, int k) {

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

if (n % i == 0 && --k == 0) return i;

return -1;

}

};

花花酱 LeetCode 952. Largest Component Size by Common Factor

By zxi on December 1, 2018

Problem

Given a non-empty array of unique positive integers A, consider the following graph:

There are A.length nodes, labelled A[0] to A[A.length - 1];
There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: [4,6,15,35]
Output: 4

Example 2:

Input: [20,50,9,63]
Output: 2

Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8

Note:

1 <= A.length <= 20000
1 <= A[i] <= 100000

Solution: Union Find

For each number, union itself with all its factors.

E.g. 6, union(6,2), union(6,3)

Time complexity: \( O(\Sigma{sqrt(A[i])}) \)

Space complexity: \( O(max(A)) \)

C++

// Author: Huahua, running time: 148 ms

class DSU {

public:

DSU(int n): p_(n) {

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

p_[i] = i;

}

void Union(int x, int y) {

p_[Find(x)] = p_[Find(y)];

}

int Find(int x) {

if (p_[x] != x) p_[x] = Find(p_[x]);

return p_[x];

}

private:

vector<int> p_;

};

class Solution {

public:

int largestComponentSize(vector<int>& A) {

int n = *max_element(begin(A), end(A));

DSU dsu(n + 1);

for (int a : A) {

int t = sqrt(a);

for (int k = 2; k <= t; ++k)

if (a % k == 0) {

dsu.Union(a, k);

dsu.Union(a, a / k);

}

unordered_map<int, int> c;

int ans = 1;

for (int a : A)

ans = max(ans, ++c[dsu.Find(a)]);

return ans;

}

};

Python3

# Author: Huahua, running time: 3432 ms

class Solution:

def largestComponentSize(self, A):

p = list(range(max(A) + 1))

def find(x):

while p[x] != x:

p[x] = p[p[x]]

x = p[x]

return x

def union(x, y):

p[find(x)] = p[find(y)]

for a in A:

for k in range(2, int(math.sqrt(a) + 1)):

if a % k == 0:

union(a, k)

union(a, a // k)

return collections.Counter([find(a) for a in A]).most_common(1)[0][1]