Alone in Couple – GeeksforGeeks

In a celebration of N individuals, every individual is denoted by an integer. {Couples} are represented by the identical quantity. Discover out the one single individual on the social gathering of {couples}.

Examples:

Enter: N = 5, arr = {1, 2, 3, 2, 1}
Output: 3
Explaination: Solely the quantity 3 is single.

Enter: N = 11, arr = {1, 2, 3, 5, 3, 2, 1, 4, 5, 6, 6}
Output: 4
Explaination: 4 is the one single.

Naive method: To unravel the issue observe the under steps:

• Kind the array of integers.
• Now, traverse the array by screening two parts directly. We do that as a result of numbers current in a pair can be current in a bunch of two and would seem consecutively in a sorted array.
• After we come throughout a bunch of two parts that aren’t the identical, the minimal of the 2 parts or the primary aspect of the group within the sorted array is the one aspect within the social gathering of {couples}.

Illustration of the above method:

For e.g., we take an array of integers = {1, 1, 2, 3, 2, 3, 4, 5, 6, 5, 4}

After sorting the array turns into = {1, 1,  2, 2,  3, 3,  4, 4,   5, 5,  6}

As we will see, 6 is the one aspect that doesn’t have its pair. 

The time complexity of this algorithm can be O(N log N), as we’re sorting the array of numbers first which is the costliest operation.

Alone in Couple utilizing Bitwise Operator:

To know the answer to this drawback, first, we now have to grasp the Bitwise Operator, XOR. The reality desk of XOR is given under for reference:

Reality Desk for XOR

To rapidly recap a very helpful property of XOR: When operated on two similar numbers, it returns 0. This property might be simply deduced by the reality desk given above. When a quantity can be XOR’ed with itself the binary illustration of each A and B within the above reality desk can be the identical and end in 0 in bits of all positions.

For Eg:

A quantity XOR’ed with itself at all times returns 0.

On the social gathering, we now have two numbers which can be similar to one another, which belong to the {couples}. If they’re XOR’ed with one another, they’ll return the reply as 0.   To have a full understanding of the answer, we have to know that XOR is associative, i.e., the order of grouping doesn’t matter when a number of XOR operations are completed. For e.g.

The order of grouping doesn’t change the results of the expression.

So, if we XOR all of the numbers of attendees with one another, we’ll get hold of the quantity which doesn’t have its pair.
A pictorial illustration of the identical idea is given with the instance under:

The duplicate numbers when XOR’ed will cancel one another regardless of the order due to the associative property of XOR.

Comply with the steps to resolve the issue:

• Declare an integer variable ‘x‘ with the beginning worth as 0.
• Iterate via the array of numbers representing the attendees, and 
  • Maintain updating the ‘x’ with every iteration after performing XOR with the present aspect.
• The integer ‘x‘ represents the one Attendee on the social gathering.

Under is the implementation for the above method:

Time complexity: O(N), the place N is the dimensions of the array as we’re traversing via the array as soon as.
Auxiliary House: O(1)