10(April) Party of Couples
10. Party of Couples
The problem can be found at the following link: Question Link
Problem Description
You are given an integer array arr[]
of size n
, representing n
number of people in a party, each person is denoted by an integer. Couples are represented by the same number, i.e., two people have the same integer value, it means they are a couple. Find out the only single person in the party of couples.
Example:
Input:
n = 5
arr = {1, 2, 3, 2, 1}
Output:
3
Explanation: Only the number 3 is single.
Input:
n = 11
arr = {1, 2, 3, 5, 3, 2, 1, 4, 5, 6, 6}
Output:
4
Explanation: 4 is the only single.
Your Task:
You do not need to read input or print anything. Your task is to complete the function findSingle()
which takes the size of the array n
and the array arr[]
as input parameters and returns the only single person.
Expected Time Complexity: O(n) Expected Auxiliary Space: O(1)
Constraints:
1 β€ n β€ 10^4
1 β€ arr[i] β€ 10^6
My Approach
XOR Operation:
Initialize a variable
single
to 0.Traverse through the array and perform bitwise XOR operation of each element with the
single
variable.At the end,
single
will hold the value of the single person in the party.
Return:
Return the value of
single
.
Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), as we traverse through the array once.
Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of additional space.
Code (C++)
class Solution{
public:
int findSingle(int n, int arr[]) {
int single = 0;
for(int i = 0; i < n; i++) {
single ^= arr[i];
}
return single;
}
};
Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated