Check If It Is A Good Array - Leetcode Solution

Problem Statement:

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.

Example 1: Input: nums = [12,5,7,23] Output: true Explanation: Pick numbers 5 and 7. 53 + 7(-2) = 1

Solution Approach:

The most important observation in this problem which can be deduced from the mathematical induction and factorisation of the numbers in the binary form. Consider the example set of numbers: a = {2, 4, 6}. These numbers have binary representations of 10, (100)2, (110)2 respectively. Now add these together: 10+100+110 = 1000 which is the binary representation of 8. Notice that the only binary digit that is 1 in this example is the highest bit. Now, consider multiplying these numbers by −1,1,−1, respectively, and adding them. The result is 2−4+6=4, which is twice the sum of the positive numbers. What is going on here? Recall that taking a binary bit string of n digits and adding 1 to it has the effect of flipping all n bits. Thus the number of odd positions with a 1 bit and the number of even positions with a 1 bit are odd.

Algorithm:

1. Find GCD of all elements in the nums array.
2. If GCD == 1, then return true because you can always multiply any element by 1 to get one.
3. If GCD > 1, then return false because it is not possible to choose any set of elements from the array that can add up to 1.

Code:

def isGoodArray(nums): gcd = nums[0] for num in nums: gcd = math.gcd(gcd, num)

return gcd == 1

Time complexity: O(n log max(num))

1