Check if it is a good array

Array Math Number Theory

63.4% acceptance

Feb 25, 2026

569

385

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_good_array(nums: Vec<i32>) -> bool {
    fn gcd(a: i32, b: i32) -> i32 {
      if b == 0 { a } else { gcd(b, a % b) }
    }
    let g = nums.iter().fold(0, |acc, &x| gcd(acc, x));
    g == 1
  }
}