Skip to main content

1250. Check If It Is a Good Array

hard

Decide whether you can pick a subset of integers from an array and assign integer multipliers so the weighted sum is exactly 1. Bezout's identity collapses it to: gcd of the array equals 1.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

Example 1

Input
nums = [12,5,7,23]
Output
true

Explanation: Pick numbers 5 and 7. 5*3 + 7*(-2) = 1.

Example 2

Input
nums = [29,6,10]
Output
true

Explanation: Pick numbers 29, 6 and 10. 29*1 + 6*(-3) + 10*(-1) = 1.

Example 3

Input
nums = [3,6]
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Bezout's identity: integer linear combinations a*x + b*y span exactly the multiples of gcd(x, y). Generalizes to any number of integers.

Hint 2

So the achievable sums from the whole array are exactly the multiples of gcd(nums).

Hint 3

1 is achievable iff gcd(nums) == 1.

Hint 4

Reduce the array with gcd left-to-right: g = nums[0]; g = gcd(g, nums[i]) for each i. Return g == 1. Early exit when g hits 1.

Solution approach

Reveal approach

Bezout's identity applied across the array: the set of integers expressible as a linear combination of array elements with integer coefficients is exactly the set of multiples of gcd(nums). 1 lies in this set iff gcd(nums) == 1. Reduce the array with a running gcd: start with g = nums[0], then for each subsequent element n in nums, set g = gcd(g, n). Return g == 1. Early exit the moment g == 1 — the gcd is monotonically non-increasing as you fold in more elements. O(n * log(max_value)) time, O(1) space.

Complexity

Time
O(n log n)
Space
O(1)

Related patterns

  • math
  • number-theory
  • euclidean-algorithm

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Check If It Is a Good Array and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →