Check If It Is a Good Array

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 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

    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 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:
        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

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Algorithm, Python, Software Puzzle. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s