Check If It Is a Good Array

Check If It Is a Good Array

What is this problem about?

The "Check If It Is a Good Array interview question" is a mathematical number theory problem. An array is "good" if you can pick a subset of numbers and find a set of integers (coefficients) such that the linear combination of the subset and these integers equals 1. For example, if you pick $x$ and $y$, you need to find $a$ and $b$ such that $ax + by = 1$.

Why is this asked in interviews?

This "Check If It Is a Good Array coding problem" is asked by companies like Google and Jump Trading to test a candidate's knowledge of Bézout's Identity. It evaluates if you can look past the surface of a problem to find the underlying mathematical principle. It’s a test of "Number Theory" and "Math interview pattern" logic.

Algorithmic pattern used

This problem follows the Greatest Common Divisor (GCD) pattern based on Bézout's Identity.

1. The Theorem: Bézout's Identity states that for any integers $x$ and $y$, there exist integers $a$ and $b$ such that $ax + by = \gcd(x, y)$.
2. Extended Rule: This extends to any number of integers. The smallest positive integer that can be expressed as $\sum a_i x_i$ is the GCD of all $x_i$.
3. Logic: An array is "good" if the GCD of all numbers in the array (or any subset) is 1. If the GCD of the whole array is 1, then a subset with GCD 1 definitely exists.

Example explanation

Array: [12, 5, 7]

1. $\gcd(12, 5) = 1$.
2. Since we found a pair with GCD 1, we can form the sum 1. (e.g., $-2 imes 12 + 5 imes 5 = -24 + 25 = 1$). Result: True. Array: [10, 6, 4]
3. $\gcd(10, 6, 4) = 2$.
4. The smallest positive sum we can make is 2. We can never make 1. Result: False.

Common mistakes candidates make

• Subset Search: Trying to find all possible subsets ($O(2^N)$), which is unnecessary and inefficient.
• Misunderstanding GCD: Not realizing that if the GCD of the whole array is 1, the condition is satisfied.
• Initial GCD: Starting the GCD calculation with 0 or the first element correctly (the GCD of 0 and $x$ is $x$).

Interview preparation tip

Refresh your knowledge of basic number theory: GCD, LCM, and Bézout's Identity. These concepts appear frequently in "Hard" level math-oriented coding problems.