- Published on

# Two Out of Three.

Welcome to yet-another 26th edition of my coding diary where I solve a coding challenge daily and share my thought process with some interesting ways to solve the problem.

Well, let's get started.

**Problem of the day** - Two Out of Three

**Tag** - Easy

Given three integer arrays `nums1`

, `nums2`

, and `nums3`

, return *a distinct array containing all the values that are present in at least two out of the three arrays. You may return the values in any order*.

**Example 1:**

**Input:** nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
**Output:** [3,2]

The simplest explanation of the problem statement would be to find the numbers which are present in at least 2 arrays.

By looking at the problem, I could imagine of having three hashmaps to check, if a number is present in all three hashmaps or not. (I know, its the worst one! don't worry I will optimize it going forward)

**Straight forward approach** -

- Maintain three hashmaps
- Iterate over each array and set the values to their respective hashmap
- Loop from 0 to 100 (max possible value as per the constraints) and find which element is present in at least 2 array

I am not going to write code for this approach. It's the simplest approach and the worst one.

In order to optimize it further, I re-read the problem statement and this time, constraints caught my attention. Max possible length and element of given arrays is 100.

Whenever, I get small constraints limit I think of using an array of fixed lengths instead of a heavy hashmap.

So, my new approach is to keep a 2D array of 3 rows and 100 columns. For each array, I will set the value in it's respective row.

**Here is the code**

`class Solution {public: vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) { int list[3][101] = {0}; vector<int> res; // set value for(int num: nums1) list[0][num] = 1; for(int num: nums2) list[1][num] = 1; for(int num: nums3) list[2][num] = 1; // check if found in atleast 2 for(int i=0;i<=100;i++) { if(list[0][i] + list[1][i] + list[2][i] >= 2) res.push_back(i); } return res; }};`

The code explains everything. (in case it's not, do reach out to me)

Umm, but I was not kind-of-satisfied with this approach. It's cool and working smoothly but let's find some other approach.

You guys are not gonna believe this but we can solve this with `bit-masking`

too.

**Idea behind the algorithm**

- Keep an array of fixed length
- Forgiven first array, we XOR all elements with 1 (in binary 001), for the second array, XOR all elements with 2 (in binary 010), and for the third array, XOR all the elements with 4 (in binary 100).
- If an element only appears once, possible values are
`001, 010, 100`

. If the element appears twice possible values are`011, 101, 110`

and if an element appears in all three arrays, possible values would be`111`

. - Here we can see if the final value for an element is 3,5,6,7 which means this element has appeared twice.

**The code behind this interesting approach**

```
class Solution {public: vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) { vector<int> res; int list[129] = {}; for(int num: nums1) list[num] |= 1; for(int num: nums2) list[num] |= 2; for(int num: nums3) list[num] |= 4; for(int i=0;i<=100;i++) { if(list[i] == 3 || list[i] >= 5) res.push_back(i); }
return res; }};
```

Another trick would be to directly check the number of set bits in the final value. If it's greater than equal to 2, we pick that answer.

It was a really-really nice problem to solve. I enjoyed the bit-masking approach. It motivates me to never settle for the brute-force approach. I would love to hear if you have any other approach to solve this.

Thanks for being part of my daily-code-workout journey. As always, if you have any thoughts about anything shared above, don't hesitate to reach out.

You might like previous editions of my coding diary