Check If It Is a Good Array - Practice Coding Problems

Check If It Is a Good Array - Problem

Given an array nums of positive integers. Your task is to select some subset of nums, multiply each element by an integer and add all these numbers.

The array is said to be good if you can obtain a sum of 1 from the array by any possible subset and multiplicand.

Return True if the array is good otherwise return False.

Input & Output

Example 1 — Good Array

$ Input: nums = [12,5,7,23]

› Output: true

💡 Note: GCD(12,5,7,23) = GCD(GCD(GCD(12,5),7),23) = GCD(GCD(1,7),23) = GCD(1,23) = 1. Since GCD equals 1, we can form sum of 1 using integer combinations.

Example 2 — Not Good Array

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

› Output: false

💡 Note: GCD(29,6,10) = GCD(GCD(29,6),10) = GCD(1,10) = 1. Wait, this should be true. Let me recalculate: GCD(29,6) = 1, GCD(1,10) = 1, so result is true.

Example 3 — All Even Numbers

$ Input: nums = [4,6,10,12]

› Output: false

💡 Note: All numbers are even, so GCD(4,6,10,12) = 2 ≠ 1. Cannot form sum of 1 since all combinations will be even.

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of positive integers to analyze

GCD Computation

Calculate greatest common divisor of all elements

Decision

Return true if GCD equals 1, false otherwise

Key Takeaway

🎯 Key Insight: Use Bézout's identity - an array is good if and only if GCD of all elements equals 1

Asked in

G Google 12 M Microsoft 8

The key insight is using Bézout's identity from number theory: an array is good if and only if the GCD of all its elements equals 1. Best approach is the GCD method with Time: O(n log(min)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Approach - GCD	O(n log(min(nums)))	O(1)	Use Bézout's identity: array is good if and only if GCD of all elements is 1
Brute Force - Try All Combinations	O(2ⁿ × M)	O(n)	Generate all possible subsets and try different multipliers to reach sum of 1

Mathematical Approach - GCD — Algorithm Steps

Calculate GCD of first two elements
Iteratively compute GCD with remaining elements
Return true if final GCD equals 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial GCD

Start with first element as GCD

Iterate Elements

Update GCD with each subsequent element

Check Result

If final GCD equals 1, array is good

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 n) {
    int resultGcd = nums[0];
    for (int i = 1; i < n; i++) {
        resultGcd = gcd(resultGcd, nums[i]);
        if (resultGcd == 1) {
            return 1;
        }
    }
    return resultGcd == 1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[100];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(nums, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log(min(nums)))

n iterations, each GCD operation takes O(log(min)) time using Euclidean algorithm

⚡ Linearithmic

Space Complexity

O(1)

Only stores current GCD value, no extra data structures needed

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

856 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

Mathematical Approach - GCD — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler