It is a Monday. Things are going well for me; hope the same for you.
I decided to tackle the next problem in a list at LeetCode. The problem is LeetCode 136 Single Number. Not sure if problems change with time so if interested please visit the LeetCode site and get the requirements directly from them.
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory? Constraints: o 1 <= nums.length <= 3 * 104 o -3 * 104 <= nums[i] <= 3 * 104 o Each element in the array appears twice except for one element which appears only once.
Apparently we are given an array of integers in which all but one number is unique. Our mission is to locate such number and display its value.
We will attempt to solve the problem using two passes. In the first we will use a set and in the second the function XOR. The reason for this is due to the fact that for the first approach there is little to do but choose the proper class. In the second approach we need to implement the problem in linear fashion but without extra memory.
As I am typing this post, we could use the first entry in the array instead of an extra variable. Of course we would modify the contents of the array. I prefer, if possible not to add potential issue by altering parameters.
class Solution {
public int singleNumber(int[] nums) {
}
}
The signature for the method in question is provided by LeetCode.
I will attempt to solve the problem using Java and the VSCode IDE on a Windows 10 machine. The simplest thing is to solve the problem directly on the IDE provided by LeetCode.
2,2,1 main <<< arr: [2, 2, 1] main <<< output: 1 main <<< output: 1 4,1,2,1,2 main <<< arr: [4, 1, 2, 1, 2] main <<< output: 4 main <<< output: 4 1 main <<< arr: [1] main <<< output: 1 main <<< output: 1 -2,1,1,-1,-1 main <<< arr: [-2, 1, 1, -1, -1] main <<< output: -2 main <<< output: -2
The first line contains the values for the int[] array.
It seems that our test code reads the values, created an int[] and populates it. The contents of the array are displayed.
It seems we have two versions. Both versions seem to return the same result which by inspection appears to be correct.
All but the last test case was provided by LeetCode.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the input into a int[] ****
int[] arr = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close the buffere reader ****
br.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** solve and display result ****
System.out.println("main <<< output: " + singleNumber0(arr));
// **** solve and display result ****
System.out.println("main <<< output: " + singleNumber(arr));
}
This is the test code that we developed to collect the data for the array, generate the array, pass the array to the function in question, and display the result. If you solve the problem using the IDE provided by LeetCode you will not require generating test code. THIS CODE IS NOT PART OF THE SOLUTION.
/**
* Given a non-empty array of integers nums,
* every element appears twice except for one.
* Find that single one.
*
* Will use a set on this first attempt.
*
* Runtime: 23 ms, faster than 9.88% of Java online submissions.
* Memory Usage: 39.1 MB, less than 67.29% of Java online submissions.
*/
static int singleNumber0(int[] nums) {
// **** initialization ****
TreeSet<Integer> set = new TreeSet<Integer>();
// **** traverse the array ****
for (int i = 0; i < nums.length; i++) {
// **** check if in set ****
if (set.contains(nums[i])) {
set.remove(nums[i]);
} else {
set.add(nums[i]);
}
}
// **** return single number ****
return set.first();
}
This is the first attempt at the solution. We use a data structure / class to hold duplicates. The first time we add the value. The second time we remove the value. When all numbers are processed we will have the answer left in the data structure. In our case we used a TreeSet.
/**
* Given a non-empty array of integers nums,
* every element appears twice except for one.
* Find that single one.
*
* Will use XOR on the second attempt.
*
* Runtime: 1 ms, faster than 95.11% of Java online submissions.
* Memory Usage: 38.8 MB, less than 94.63% of Java online submissions.
*/
static int singleNumber(int[] nums) {
// **** initialization ****
int xor = nums[0];
// **** loop through all entries in the array ****
for (int i = 1; i < nums.length; i++)
xor ^= nums[i];
// **** return single number ****
return xor;
}
In this second attempt, we will not use extra memory. We will compute the XOR of all elements. The result will remain in the variable xor.
The performance and memory used is displayed in the comments section of each function.
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, 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