The weather is slowly changing in the Twin Cities of Minneapolis and St. Paul. Days are getting shorter and the temperature is going down. Winter appears to be around the corner. That said; the vegetation in the area is not as dry as other years. Hopefully we will have a not so cold winter.
In addition, today is October 12th, the actual day that Christopher Columbus discovered America. The day was celebrated yesterday in the USA. Note that Christopher Columbus landed in what is today Central America and went south. He did not put a foot on North America.
I continue watching and experimenting with the contents of the on-line course on Python. I am currently in Lesson 4. In addition I am reading the associated book “Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and The Cloud 1st Edition” by Paul Deitel and Harvey Deitel.
Earlier today I selected LeetCode 1304 Find N Unique Integers Sum up to Zero. This problem is rated Easy.
Given an integer n, return any array containing n unique integers such that they add up to 0. Constraints: o 1 <= n <= 1000
We are given an integer `n` and we need to generate an array containing unique integers that add up to zero. It looks quite open for multiple solutions.
We will attempt to solve this problem using the Java programming language and the VSCode IDE on a Windows computer.
public int[] sumZero(int n) {
}
The signature for the problem is quite simple. We are given as input the integer `n` and we need to return an array that meets the requirements.
5 main <<< n: 5 main <<< output: [1, 2, 3, 4, -10] main <<< output: [-1, -2, 0, 1, 2] 3 main <<< n: 3 main <<< output: [1, 2, -3] main <<< output: [-1, 0, 1] 1 main <<< n: 1 main <<< output: [0] main <<< output: [0] 2 main <<< n: 2 main <<< output: [1, -1] main <<< output: [-1, 1] 4 main <<< n: 4 main <<< output: [1, 2, 3, -6] main <<< output: [-1, -2, 1, 2]
Since I worked on the problem on my computer I have to generate a test scaffold. If you decide to use the on-line IDE provided by LeetCode, you would not have to write test code. The test code IS NOT PART OF THE SOLUTION!
Our test code seems to read the input line and then display the value assigned to the variable `n`.
Two different results are generated. I tried a couple approaches and they booth seem to perform similarly. One approach is simpler than the other.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** ****
int n = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< n: " + n);
// **** call function of interest and display result ****
System.out.println("main <<< output: " + Arrays.toString(sumZero0(n)));
// **** call function of interest and display result ****
System.out.println("main <<< output: " + Arrays.toString(sumZero(n)));
}
Our test code uses a buffered reader to read the input line and extract the value of `n`. The value is then displayed to verify that so far all is well. We then call the two implementations and display their associated results.
/**
* Given an integer n, return any array containing
* n unique integers such that they add up to 0.
*
* 42 / 42 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 39.2 MB
*/
static public int[] sumZero0(int n) {
// **** initialization ****
int[] arr = new int[n];
int sum = 0;
// **** populate the arr[] - O(n) ****
for (int i = 0; i < n - 1; i++) {
// **** populate this entry ****
arr[i] = i + 1;
// **** update the sum ****
sum += arr[i];
}
// **** set the last entry in arr[] ****
arr[n - 1] = -sum;
// **** return arr[] ****
return arr;
}
We declare the array which we will populate with a set of `unique` integers adding up to `zero`.
We start by initializing the arr[] which we will populate and return and a sum.
We then loop setting the first `n – 1` entries to monotonically ascending integers. We add each integer to the sum.
After the loop we assign to the last entry in arr[] the negative value of `sum`. This way, we will be able to fulfill the requirement that the `unique` elements should sum up to `zero`.
The arr[] is then returned.
/**
* Given an integer n, return any array containing
* n unique integers such that they add up to 0.
*
* 42 / 42 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 39.1 MB
*/
static public int[] sumZero(int n) {
// **** initialization ****
int[] arr = new int[n];
// **** determine if n is even or odd ****
boolean even = (n % 2 == 0 ? true : false);
// **** populate the array - O(n / 2) ****
for (int i = 0; i < n / 2; i++) {
// **** fill left cell ****
arr[i] = (i + 1) * -1;
// **** fill right cell ****
arr[i + (n / 2) + (even ? 0 : 1)] = (i + 1);
}
// **** return arr[] ****
return arr;
}
We start initializing the arr[] and determining if `n` is odd or even.
We enter a loop in which we add negative integers to the left side in arr[] and positive integers to the right side. If there is an odd number of integers, the center value will remain set to `zero`. By adding all values we are able to sum all values to `zero`. Perhaps a little faster but more complicated. Actually the run time of both implementations is the same.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John