1819. Number of Different Subsequences GCDs

Description

You are given an array nums that consists of positive integers.

The GCD of a sequence of numbers is defined as the greatest integer that divides all the numbers in the sequence evenly.

• For example, the GCD of the sequence [4,6,16] is 2.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

• For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

Return the number of different GCDs among all non-empty subsequences of nums.

 

Example 1:

Input: nums = [6,10,3]
Output: 5
Explanation: The figure shows all the non-empty subsequences and their GCDs.
The different GCDs are 6, 10, 3, 2, and 1.

Example 2:

Input: nums = [5,15,40,5,6]
Output: 7

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 2 * 105

 

Solutions

Solution: Math

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

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const countDifferentSubsequenceGCDs = function (nums) {
  const maxNum = Math.max(...nums);
  const factors = Array.from({ length: maxNum + 1 }, () => 0);
  let result = 0;

  const gcd = (a, b) => (b ? gcd(b, a % b) : a);

  for (const num of nums) {
    for (let a = 1; a ** 2 <= num; a++) {
      if (num % a) continue;
      const b = num / a;

      factors[a] = gcd(num, factors[a]);
      factors[b] = gcd(num, factors[b]);
    }
  }

  for (let num = 1; num <= maxNum; num++) {
    if (num === factors[num]) {
      result += 1;
    }
  }

  return result;
};