1819. Number of Different Subsequences GCDs (Leetcode)

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

Example: 2

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

Output: 7

Constraints:

• 1 <= nums.length <= 10 ^ 5
• 1 <= nums[i] <= 2 * 10 ^ 5

Main Intuition:

• If there are some numbers that can be divided by N, say (A, B, C and D), then, if we consider GCD(A, B, C, D) and it equals N, then we can say that we have found a subsequence that can form gcd of N.
• For this to happen, all numbers in that group, (in our example A, B, C and D) should be divided by N.

Implementation:

• So now what we have to do is to go through all values from 1 to N (in our case 2 * 10⁵).
• Then for each of this number we will check whether or not this value can be formed as a gcd.
• To do this we will go through all multiples of this current number, say N.(N, 2 * N, 3 * N, ...).
• If that number is found we will compute its gcd with other numbers we find along the way.
• In the code we are taking the first element to be 0. This is because adding 0 will not affect the gcd of any number.

Full Code (Java): class Solution { public int countDifferentSubsequenceGCDs(int[] nums) { // created a set of all possible gcd values boolean[] set = new boolean[2 * 100000 + 5]; // setting all of the numbers as true, if they are found in nums array for(int i : nums) set[i] = true; // initializing our gcd array to check whether gcds[N] == N int[] gcds = new int[set.length]; // checking if the gcd value can be derived or not for(int gcd = 1; gcd < set.length; gcd++) { // going through all possible multiples of gcd value which we want to check for(int i = gcd; i < gcds.length; i += gcd) { // if the multiple is found we will compute its gcd with already added elements // initially the value of gcds[gcd] is kept 0, // so that it won't affect the overall computed gcd for that particular multiple of gcd if(set[i]) { gcds[gcd] = gcd(gcds[gcd], i); } } } // checking if gcds[i] == i int count = 0; for(int i = 1; i < set.length; i++) { if(gcds[i] == i) { count++; } } return count; } int gcd(int a, int b) { if(a == 0) return b; return gcd(b % a, a); } }