Description
You are given an array of positive integers nums.
An array arr is called product equivalent if prod(arr) == lcm(arr) * gcd(arr), where:
prod(arr) is the product of all elements of arr.gcd(arr) is the GCD of all elements of arr.lcm(arr) is the LCM of all elements of arr.
Return the length of the longest product equivalent subarray of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
The term gcd(a, b) denotes the greatest common divisor of a and b.
The term lcm(a, b) denotes the least common multiple of a and b.
Example 1:
Input: nums = [1,2,1,2,1,1,1]
Output: 5
Explanation:
The longest product equivalent subarray is [1, 2, 1, 1, 1], where prod([1, 2, 1, 1, 1]) = 2, gcd([1, 2, 1, 1, 1]) = 1, and lcm([1, 2, 1, 1, 1]) = 2.
Example 2:
Input: nums = [2,3,4,5,6]
Output: 3
Explanation:
The longest product equivalent subarray is [3, 4, 5].
Example 3:
Input: nums = [1,2,3,1,4,5,1]
Output: 5
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 10
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution:
def maxLength(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
max_p = lcm(*nums) * max(nums)
for i in range(n):
p, g, l = 1, 0, 1
for j in range(i, n):
p *= nums[j]
g = gcd(g, nums[j])
l = lcm(l, nums[j])
if p == g * l:
ans = max(ans, j - i + 1)
if p > max_p:
break
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | class Solution {
public int maxLength(int[] nums) {
int mx = 0, ml = 1;
for (int x : nums) {
mx = Math.max(mx, x);
ml = lcm(ml, x);
}
int maxP = ml * mx;
int n = nums.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
int p = 1, g = 0, l = 1;
for (int j = i; j < n; ++j) {
p *= nums[j];
g = gcd(g, nums[j]);
l = lcm(l, nums[j]);
if (p == g * l) {
ans = Math.max(ans, j - i + 1);
}
if (p > maxP) {
break;
}
}
}
return ans;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
private int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | class Solution {
public:
int maxLength(vector<int>& nums) {
int mx = 0, ml = 1;
for (int x : nums) {
mx = max(mx, x);
ml = lcm(ml, x);
}
long long maxP = (long long) ml * mx;
int n = nums.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
long long p = 1, g = 0, l = 1;
for (int j = i; j < n; ++j) {
p *= nums[j];
g = gcd(g, nums[j]);
l = lcm(l, nums[j]);
if (p == g * l) {
ans = max(ans, j - i + 1);
}
if (p > maxP) {
break;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | func maxLength(nums []int) int {
mx, ml := 0, 1
for _, x := range nums {
mx = max(mx, x)
ml = lcm(ml, x)
}
maxP := ml * mx
n := len(nums)
ans := 0
for i := 0; i < n; i++ {
p, g, l := 1, 0, 1
for j := i; j < n; j++ {
p *= nums[j]
g = gcd(g, nums[j])
l = lcm(l, nums[j])
if p == g*l {
ans = max(ans, j-i+1)
}
if p > maxP {
break
}
}
}
return ans
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func lcm(a, b int) int {
return a / gcd(a, b) * b
}
|