Number of Different Subsequences GCDs - Practice Coding Problems

Number of Different Subsequences GCDs - Problem

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.

Input & Output

Example 1 — Small Array

$ Input: nums = [6,10,3]

› Output: 5

💡 Note: All possible subsequences and their GCDs: [6]→6, [10]→10, [3]→3, [6,10]→2, [6,3]→3, [10,3]→1, [6,10,3]→1. Unique GCDs: {1,2,3,6,10}, so answer is 5.

Example 2 — Identical Elements

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

› Output: 7

💡 Note: With elements 5,15,40,5,6, we can form subsequences with GCDs: 1,2,3,5,6,15,40. Total unique GCDs = 7.

Example 3 — Single Element

$ Input: nums = [42]

› Output: 1

💡 Note: Only one subsequence [42] with GCD = 42. Answer is 1.

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ nums[i] ≤ 2 × 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [6, 10, 3] with positive integers

Process

Find all possible subsequence GCDs efficiently

Output

Count of unique GCDs: 5

Key Takeaway

🎯 Key Insight: Rather than generating exponentially many subsequences, test each potential GCD by collecting its multiples and verifying their actual GCD

Asked in

G Google 15 a Amazon 12

The key insight is to avoid generating all 2^n subsequences by instead testing each possible GCD value. For each candidate GCD g from 1 to max element, collect all array elements divisible by g and check if their actual GCD equals g. Best approach has Time: O(max × n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Subsequences	O(2^n × n)	O(2^n)	Generate every possible non-empty subsequence and compute GCD of each
Divisor-Based Approach	O(max × n)	O(n)	Check each possible GCD value by finding its multiples in the array

Generate All Subsequences — Algorithm Steps

Generate all 2^n - 1 non-empty subsequences using bit manipulation
For each subsequence, compute GCD of all elements
Add each unique GCD to a set
Return the size of the set

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Array

Start with array [6, 10, 3]

Generate Subsequences

Create all 2^3-1 = 7 non-empty subsequences

Compute GCDs

Calculate GCD for each subsequence and count unique values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int solution(int* nums, int numsSize) {
    int gcds[200001] = {0}; // Track unique GCDs
    int count = 0;
    
    // Generate all non-empty subsequences using bitmask
    for (int mask = 1; mask < (1 << numsSize); mask++) {
        int subseq[20];
        int subseqSize = 0;
        
        for (int i = 0; i < numsSize; i++) {
            if (mask & (1 << i)) {
                subseq[subseqSize++] = nums[i];
            }
        }
        
        // Calculate GCD of current subsequence
        int currentGcd = subseq[0];
        for (int j = 1; j < subseqSize; j++) {
            currentGcd = gcd(currentGcd, subseq[j]);
        }
        
        if (!gcds[currentGcd]) {
            gcds[currentGcd] = 1;
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

2^n subsequences, each requiring O(n) time to compute GCD

⚠ Quadratic Growth

Space Complexity

O(2^n)

Storing all possible subsequences and their GCDs

⚠ Quadratic Space

25.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler