Lonely Element In an Array [Two Important Problems]

[Note: The problem mentioned below are not so hard to solve if we ignore the restricted complexities.  Also there are other methods to solve this problems, this post is about solving this problems using bit-manipulation.]
Problem 1:   Given an array where every element occurs two times or in general even no of times except the one element which occurs only once or in general odd number of times. Find that element. The time and space Complexity of the solution must be O(N) and O(1) respectively.

The key concept here is bitwise-xor (^).
some properties of xor:
   (i) The xor of a number with itself is Zero.  i.e. a ^ a = 0
   (ii) The xor of a number with Zero is the same number. i.e. a ^ 0 = a;
   (iii) Associativity i.e. a ^ (b ^ c) = (a ^ b) ^ c;

so in the given array if we do the bitwise xor of entire array, the numbers occurring even number of  times will become zero. And the number occurring only odd number of times will xor with zero to result into itself.

Ex.
(i)  A = [ 3,  3,  4,  4,  7,  7,  5].
      xor_of_A = 3 ^ 3 ^ 4 ^ 4 ^ 7 ^ 7 ^ 5 = 5;

(ii)  B = [3,  5,  3,  5,  6,  6,  6];
       xor_of_B = 3 ^ 5 ^ 3 ^  5 ^ 6 ^ 6 ^ 6 = 6;

here's my code:

Problem 2:   Given an array where every element occurs three times , except one element which occurs only once. Find the element that occurs once.
Expected time and space complexities are O(N) and O(1) respectively.

If we follow the previous problem approach , since each element in the array is occurring odd number of times, it will yield the xor of all the element in the array.

The idea here is to store the elements that occurred  once and twice in two separate variables "ones" and "twos" and as we encounter an element third time we remove that element from ones and twos, continue this process for all the element. At the end the variable "ones" will have the element that occured once.

The variable "ones" and "twos" here are storing the xor of the element occuring ones and twice respectively.
To summarize, basically for every element we xor it with the "ones"  and store the result to "ones".
If the number is repeated (twice) then we remove it from "ones" and xor it with "twos" an store the result to "twos". If that number if repeated third times we remove it from "twos". At the end the unique element is left in the variable "ones".

Equal Sum Partition problem

Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is the same.

The two partitions must have equal sum. Let say that sum is S , now the sum of the original set must be 2*S. so the sum is an even number. Taking this into consideration we can say that if the sum of the elements in the set is not even then there is no partition possible such that the sum of each partition is equal.

one more thing, if the sum of the element  of the original set is K ,  then we just have to find a subset with the sum K/2.
Suppose we found the subset with sum K/2, then since the total sum is K , the elements not belonging to this subset will add up to K/2. Hence we found the two partitions.
All we need to do is to find the subset with sum K/2 (again K is the sum of the original set).
Notice how this problem turned out to be a variation of Subset-Sum-Problem.

I have already  written a post about subset-sum-problem here, But still I want to write about here too.
Recusive approach:

so the problem now is to check if there's a subset with the sum K/2 , where K is the sum of the original set.
Imagine an empty subset in you mind. we have to pick the suitable element from the given set and place it in our imaginary subset.
The question is which element do we choose?
First thing, we cannot choose an element whose values if greater than the sum (K/2) . That will be violation, since we want our subset to have the sum (K/2).  So when we find an element with  value greater than  K/2, we just skip it.
In other case where the value of the element is not greater than the sum, we will have choice whether to include this element in our subset or not. we then recursively solve both the case and take the  case which results into our favour.


here's the solution in C++17:

Project: "A Website Notifier"

Recently I came up with the idea to create a Notifier application for codechef contests. During contests, after I solve some problem I use to see how other people in my group doing.. so I thought instead of checking everytime why not create an python app which would notify me for every new submissions done by my friends. Without any second thought i started working on the app.



Here's my project directory looks like.

The first thing to do was to get the data from the codechef website dynamically.
For that python has a library called "requests". Additionally to parse the HTML code in the data i used another library called "beautifulsoup4".
But i found that the module "requests" get the data from the webpage without letting the javascript content load. This is the big issue since the submissions on codechef are updated by javascript code.
So, next I used "chrome-driver" from library "selenium". Basically what it does is that it load the webpage first letting javascript load and then extract the data. so problem solved.

[this part of the code uses the chrome-driver, gets the data from website, calls check ()function which returns the last submission, the if last submission doesnt match with the stored one, then call the function notify(), and write the new data to json file.. all this happen for all the users in the database]

[functions: speakUp(), check(), and notify()]

Now I have the data and I parse it using "beautifulsoup". The next question is how do i notify this data on my PC. This can be done using "notify2" library, this has even the option to set the logo for the notification.

I made a json file containing name, username and the last_submission of all the people in my group at codechef. Now I can check for each username what its last submission is . If the last submissions doesnt match with the stored last_submission then I just notify it on the pc and save the newest submisson to the json file.

I made an additional function called "speackUp" which will speak up the notification message to me, (imagine my pc talking to me) , cool right !

I made the main function in the end and set all the things. I even made this project as a package, followed official packaging docs in python3.x. I will add this to my github soon.

[used libraries]


Here the demo video: [see that push notification... that's my app]

[github link : https://github.com/alpeshjamgade/codechef-notifier]