## Problem

## 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 k_{0}, k_{1}, … k_{n-1}, such that

nums[0]*k_{0} + nums[1]*k_{1} + ... + nums[n-1]*k_{n-1} = 1

where each k_{i} 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 k_{a} and k_{b} such that

a*k_{a} + b*k_{b} = 1

for given `a`

and `b`

that are relatively prime. Note that k_{a} and k_{b} exist if and only if `a`

and `b`

are relatively prime. The following code is one way of computing k_{a} and k_{b}.

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 while not found: 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 k_{a} and k_{b} in the equation

a*k_{a} + b*k_{b} = 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: print("Bad Array")

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