## Leetcode presents the following 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.

## Simple Solution

A simple solution in Python can be as follows

```   from math import gcd
from functools import reduce
def check_good(nums):
return reduce(gcd,nums) ==1
```

## Extended Problem

However the more interesting problem would be to generate the values k0, k1, … kn-1, such that
``` nums[0]*k0 + nums[1]*k1 + ... + nums[n-1]*kn-1 = 1 ```
where each ki is any integer and given that the values in `nums` are relatively prime. In other words, their only common factor is `1`.

## Discussion

Notice that we can work with any subset that is relatively prime. The simplest way to do that would be to choose the first few elements that are relatively prime.
This can be done as follows:

```    def get_good_array(arr):
g0=gcd(arr[0],arr[1])
i =2
while i < len(arr) and not g0==1:
g0 = gcd(g0,arr[i])
i+=1
return arr[:i]
```

Returning to our original problem let us simplify it so that we consider the case where we are dealing with just two numbers that are relatively prime. We are interested in computing ka and kb such that

``` a*ka + b*kb = 1 ```

for given `a` and `b` that are relatively prime. Note that ka and kb exist if and only if `a` and `b` are relatively prime. The following code is one way of computing ka and kb.

```  def find_k1k2g(a,b,g=1):
found = a-b==g or b-a==g
ka=1
kb=1
a0 = a
b0 = b
if found:
if a<b : ka = -1
else: kb = -1

if a0<b0 :
k = b0//a
ka = (k+1)
a0 = ka *a
kb = -kb
else:
k = a0//b
kb = k+1
b0= kb *b
ka = -ka
found = a0-b0==g or b0-a0==g
return (ka,kb)
```

The above code can be used to compute ka and kb in the equation
``` a*ka + b*kb = g ```

where `g` is the greatest common divisor (GCD) of `a` and `b`.

Armed with this function we can now keep track of all `k`‘s

```    multiples = []
g0=gcd(arr[0],arr[1])
multiples.append(find_k1k2g(arr[0],arr[1],g0))
array_index =2
while array_index < len(arr) and not g0==1:
g1 = gcd(g0,arr[array_index])
if g1 == arr[array_index]: multiples.clear()
else: multiples.append(find_k1k2g(g0,arr[array_index],g1))
g0=g1
array_index+=1
```

We have modified get_good_array to compute the `k`‘s. The next task is to print them out in a readable form as shown below

```        brackets = 0
(k1,k2) = multiples.pop()
while multiples) :
array_index -=1
print(k2,"*", arr[array_index], "+  ", k1 , "*" , "(")
(k1,k2) = multiples.pop()
brackets += 1
print(k2,"*", arr[array_index-1], "+ ", k1 , "*",arr[array_index-2] )
for i in range(brackets):  print(")", end="")
print("")

```

Putting the above code snippets together we have

```def prn(x,y):
if x>0 : print("+", end="")
print(x,"*", y )

def print_good_array(arr):
multiples = []
g0=gcd(arr[0],arr[1])
multiples.append(find_k1k2g(arr[0],arr[1],g0))
i =2
while i < len(arr) and not g0==1:
g1 = gcd(g0,arr[i])
if g1 == arr[i]: multiples.clear()
else: multiples.append(find_k1k2g(g0,arr[i],g1))
g0=g1
i+=1

if g0 ==1 :
multiplier= 1
(k1,k2) = multiples.pop()
while multiples :
i -=1
prn(k2*multiplier, arr[i] )
multiplier*=k1
(k1,k2) = multiples.pop()
prn(k2*multiplier,arr[i-1])
prn( k1*multiplier , arr[i-2] )
else:

```

Thus print_good_array([77,91,175,143]) prints

``` -2 * 143 -41 * 175 -5330 * 91 +6396 * 77```

``` ```

The above answer is almost there; except we would like to have the brackets removed … an exercise left for the reader