It is a Monday morning and it is garbage collection day so I had to put out on the driveway both bins. The company that provides our development with the service collects every week both garbage and recycle bins. All previous companies that I am familiar with collect garbage every week and recycle every other week. To be honest with you, my wife and I would be fine with recycling once a month and if it was not for the potential for smell during summer, garbage every other week.
Earlier this morning, I saw in my inbox a recommendation for a problem from HackerRank named Sherlock and GCD which maybe solved with a Dynamic Programming approach.
Following is my edited version of the problem. If you are interest in this problem please go to HackerRank and read the full description.
Sherlock is stuck while solving a problem: Given an array of integer values, he wants to know if there exists a subset of this array which follows these statements: o The sub-set is non-empty. o There exists no integer > 1 which divides all elements of the subset. o There are no elements in the subset which are equal to another.
In my opinion the problem is not described in a simple way. I always have a problem when requirements are not described following the KISS principle. The idea behind software engineering is to collect and refine requirements to simple language that most people (never generalize) should understand. I always (I did it; I generalized) spend time describing requirements in simple and plain language. It makes it easier to understand and follow by the development team and customer(s) alike.
The GCD of three or more numbers equals the
product of the prime factors common to all the numbers,
but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.
gcd(a, b, c) = gcd(a, gcd(b, c))
= gcd(gcd(a, b), c)
= gcd(gcd(a, c), b)
The problem seems to be around figuring out the GCD (https://en.wikipedia.org/wiki/Greatest_common_divisor) of an array of integers. We need to do two things. First compute the GCD of two integers. Then compute the GCD for an array of integers. That seems like a plan.
This question can be reduced to a simpler one. Check if there is a non-empty subset such that the Greatest Common Divisor (GCD) of the whole subset is 1. Note that if you have a and b such that GCD(a,b) is 1, then GCD(a,b,x,y,z,...) will always be 1.
This last observation came from HackerRank after I had submitted my code several times in order to perform different tests and approaches. The observation, after spending time solving and optimizing the code, seems to be easier to understand the requirements.
3 2 0 2 3 0 2 4 3 0 2 3 main <<< N: 3 main <<< a: [0, 2] main <<< solve: NO main <<< a: [0, 2, 4] main <<< solve: NO main <<< a: [0, 2, 3] main <<< solve: YES 1 3 1 2 3 main <<< N: 1 main <<< a: [1, 2, 3] main <<< solve: YES 1 2 2 4 main <<< N: 1 main <<< a: [2, 4] main <<< solve: NO 1 3 2 4 5 main <<< N: 1 main <<< a: [2, 4, 5] main <<< solve: YES 1 3 5 5 5 main <<< N: 1 main <<< a: [5, 5, 5] main <<< solve: NO 3 3 1 2 3 2 2 4 3 5 5 5 main <<< N: 3 main <<< a: [1, 2, 3] main <<< solve: YES main <<< a: [2, 4] main <<< solve: NO main <<< a: [5, 5, 5] main <<< solve: NO
I will be solving the problem on my Windows 10 machine using the Java programming language and the VSCode IDE. None of this makes a difference if you edit your code on the HackerRank web site.
The input and output format is described in the HackerRank problem description. Since I wrote my own test scaffolding, I read the lines in an order that I deemed as simple as possible. After reading the input data for an array of integers I displayed the array and then computed the result. After displaying the result I would process the next test case. I guess we could have read all the input data and then compute all the results.
By looking at the output we can easily suspect what is happening with the test scaffolding. We can now look at the actual code which IS NOT PART OF THE SOLUTION.
/**
* Test scaffoloding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read number of test cases ****
int N = Integer.parseInt(br.readLine().trim());
// ???? ????
System.out.println("main <<< N: " + N);
// **** loop once per test case ****
for (int i = 0; i < N; i++) {
// **** skip line with number of integers ****
br.readLine();
// **** read line with number of integers ****
String[] strVals = br.readLine().trim().split(" ");
// **** create and populate array of integers ****
int[] a = Arrays.stream(strVals)
.mapToInt(Integer::parseInt)
.toArray();
// ???? ????
System.out.println("main <<< a: " + Arrays.toString(a));
// **** compute and display result ****
System.out.println("main <<< solve: " + solve(a));
}
// **** close buffered reader ****
br.close();
}
We start by opening a buffered reader. We read the number of test cases and display it. We then read the number of elements in the array. We discard such information. We read the input line for the integers. We then create an array and populate it. The array is displayed to make sure all is well so far. Finally we compute the result and display it.
We continue looping until all test cases have been processed.
/**
* Compute the GCD of all integers in the specified array.
* Return result based on the GCD of the array.
* Time complexity O(n).
*/
static String solve(int[] a) {
// **** sanity check(s) ****
if (a.length == 1)
return "NO";
// **** initialization ****
int gcd = 0;
// **** traverse the array computing the GCD ****
for (int v : a) {
gcd = gcd(gcd, v);
// // ???? ????
// System.out.println("solve <<< gcd: " + gcd);
}
// **** determine and return answer ****
return (gcd == 1) ? "YES" : "NO";
}
If we are presented with an array with a single value, we immediately have an answer (check the requirements). As it was previously suggested, we need to generate the GCD for the entire array. We initialize the gcd variable and loop through all the elements in the array. For each element we compute the GCD for the current element and the running GCD.
When done, we check if the GCD is 1. If so, we return “YES”; otherwise we return “NO” (check the alternate description of the problem).
Now we just need to compute the GCD for two numbers. We will use the Euler’s method.
/**
* Compute the GDC of two integers.
* According to Euclid's method the GCD of two numbers, a, b
* is equal to GCD(b % a, a) and GCD(0, a) = a.
* Recursive approach.
*/
static int gcd(int a, int b) {
// **** base condition ****
if (a == 0)
return b;
// *** recursive call ****
return gcd(b % a, a);
}
This is a recursive approach. We have the base and the recursive condition. It helps to run a few examples using a pen and paper.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 4,864 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com