Find no. with odd no of occurence in a sequence

The problem statement states that in a given sequence of number only 1 number is occurring odd no of times and rest all the numbers are occurring even no of time.
input e.g.
                  2,3,4,1,1,2,4
                  7,5,2,3,4,4,1,2,7,7,3,4,7,5

Please try this once before proceeding ahead.

We will discuss 2 approaches to solve the problem.

Approach 1 (storing no of count in a data structure) :

We can have a hash map which stores the number of occurrence of each number in the list.
Then we can count the number of occurrence and which one is odd.

Lets take an sample input as
          

2

3

1

1

4

2

3

4

3

if we try to process this input in a hash map then we can find following map

Key	Count
2	2
3	3
1	2
4	2

we can traverse the complete map to find out the count and which one is odd.

Pros:
  1. Its simple to think as well as code
Cons:
  1. It take more space
  2. 2 iterations required; 1st iteration for counting,  2nd iteration on the map to check whose count is odd

You can find the complete source code here.
For this special case when only one item is occurring odd no of time, we can use XOR operation as well.

Approach 2 (XOR operation) :

In this approach we will XOR all the items and the final output will be the number which occurs odd no of times.

e.g.

2

3

1

1

4

2

3

4

3

                                                             
here number = 2^3^1^1^4^2^3^4^3 = 3

This solutions works only when you have a single number occurring odd no of times.

You can find the complete source code here.

Bitwise concepts

AND (&) operator :  It takes 2 operands as input and does AND operation on each and every bit of the input and provides us the output.

OR ( | ) operator : It takes 2 operands as input and does OR operation on each and every bit of the input and provides us the output.

XOR (^) operator : It takes 2 operands as input and does XOR operation on each and every bit of the input and provides us the output.

NOT(~) operator : It takes 1 operand as input and does NOT operation on the input and provides us the output.


Bit-wise XOR operations is one of the important operations which can be used for various kinds of problems.

For XOR, 1^1 = 0, 1^0=1:
   i.e. XOR on same bit becomes 0 and with different bit becomes 1.
The same concept can be used in many factors that
                                     5^5=0,
                                     3^0=3
                                     2^3^2=3
                                     7^4^2^8^2^4^8=7
so we can exploit the concepts here that in a series of XOR operations, XOR of pairs of numbers becomes 0. This can be helpful in identifying odd no of occurrence of data.

Swapping 2 numbers

Swapping 2 numbers is one of the basic question asked in the interviews or read in the syllabus.

What is Swapping?

Interchanging the values of two variable i.e. if a = 10 and b = 15, it becomes a = 15 and b = 10.

In this article, we will discuss 3 approaches in swapping 2 number.
Approach 1: (Swap using a temporary variable)

We will take a temporary variable, store the value of a in the temporary variable, copy the value of b to a and then store
                             temp = a
                             a = b
                             b = temp

Complete source code can be found here.

Approach 2: (Swap without using temporary variable)

In this Approach we will not use any extra variable, we will store the sum of both the variable in one of the first number. Then subtract the second number from the sum and store it in second number (sum - second = first) and then subtracting the second number from sum and store in first number (sum - second(which has become first now) = second)

                                           a = a+b
                                           b = a-b (here b gets the value of a)
                                           a = a-b (here a gets the value of b)

Complete source code can be found here.
Approach 3: (Swap without using temporary variable using bit-wise operator)

In this approach we will use the concept
                                         a^b = x (lets say)
                                         x^a = b, and
                                         x^b = a

so we store the xor of a and b in a itself and do alternatively xor and store it back

 lets say a=10, b=5
                                       a = a^b // a = 10^5
                                       b = a^b // b = 10^5^5 => 10
                                       a = a^b // a = 10^5^10 => 5

you can find the code here

Please provide your feedback.