### Magical usage of Bitwise operators - Get optimized solutions for many arithmatic problems

Introduction I will list some of the interesting usage of bitwise operators…

September 13, 2019

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

```
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
```

A simple brute force is the start. But, it is so simple. Lets not discuss it. You just need to make sure that result must have unique entries

Like, in two-sum problem. We used a HashSet. We can use it here as well. Again, to maintain unique elements, it added complexity.

```
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet();
int l = nums.length;
for (int i=0; i<l; i++) {
Set<Integer> vals = new HashSet();
for (int j=i+1; j<l; j++) {
if (j == i) continue;
int requiredNum = 0 - (nums[i] + nums[j]);
if (vals.contains(requiredNum)) {
List<Integer> iRes = new ArrayList();
iRes.add(requiredNum);
iRes.add(nums[j]);
iRes.add(nums[i]);
Collections.sort(iRes);
result.add(iRes);
}
if (!vals.contains(nums[j])) {
vals.add(nums[j]);
}
}
}
List<List<Integer>> r = new ArrayList(result);
return r;
}
```

Lets look at most optimized one.

- Sort the array
- Now, in a loop, start from left and right pointer.
- Keep track of sum. If we found the sum, add it. And, we need to move left and right pointer. One case is where even after moving left and right pointer, the value can be duplicate. Since, we need to avoid duplicates. We need to add a condition here to keep moving untill found a unique element.
- There is a corner case, where handling of duplicate elements has to be handled in outer loop as well. (See line ahead of for loop)

```
public List<List<Integer>> threeSum_2(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
for (int i=0; i<len; i++) {
//to avoid processing duplicate values
if (i > 0 && nums[i-1] == nums[i]) continue;
int l = i+1;
int r = len-1;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s == 0) {
List<Integer> ir = new ArrayList<>();
ir.add(nums[i]); ir.add(nums[l]); ir.add(nums[r]);
res.add(ir);
l++;
r--;
//to move over duplicate values
while (l < r && nums[l-1] == nums[l]) l++;
while (l < r && nums[r+1] == nums[r]) r--;
}
else if (s < 0) {
l++;
}
else {
r--;
}
}
}
return res;
}
```

Introduction I will list some of the interesting usage of bitwise operators…

A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…

Problem Statement Given a non-empty array of digits representing a non-negative…

This problem is a simple mathematical calculation. Lets start deriving some…

Problem Statement Given an array nums, write a function to move all 0’s to the…

Problem Statement Implement atoi which converts a string to an integer…

Introduction In this post we will see following: How to schedule a job on cron…

Introduction There are some cases, where I need another git repository while…

Introduction In this post, we will see how to fetch multiple credentials and…

Introduction I have an automation script, that I want to run on different…

Introduction I had to write a CICD system for one of our project. I had to…

Introduction Java log4j has many ways to initialize and append the desired…