Two Numbers with Odd Occurrences [TC: O(N); SC: O(1)]

two-numbers-odd-occurrences.cpp

// Problem Link: https://practice.geeksforgeeks.org/problems/two-numbers-with-odd-occurrences/0
// Good Explanation: https://www.geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array/

#include <vector>
#include <iostream>
using namespace std;

void printTwoOddOccurring(vector<int> &ar) {
  const int n = ar.size();

  // Find XOR of all the array elements
  int XOR = 0;
  for(int i = 0; i < n; ++i) 
    XOR ^= ar[i];

  // Find the rightmost set bit in the obtained XOR above and store the integer representing
  // that rightmost set bit in a variable
  const int rSetBitNum = XOR & (~(XOR - 1)); // rSetBitNum => rightmostSetBitNumber

  // Seggregate the given array elements into 2 groups,
  //  Group 1: contains numbers from ar[] which have a set bit where rSetBitNum has the set bit.
  //  Group 2: contains numbers from ar[] which doesn't have a set bit where rSetBitNum has the set bit.
  // XOR all the elements of Group 1, we'll get the first odd occurring number and,
  // XOR all the elements of Group 2, we'll get the second odd occurring number.
  int res1 = 0, res2 = 0;
  for(int i = 0; i < n; ++i)
    if(rSetBitNum & ar[i])
      res1 ^= ar[i];
    else res2 ^= ar[i];

  cout << max(res1, res2) << " " << min(res1, res2); // printing in decreasing order
}

int main() {
  int t;  cin >> t;
  while(t--) {
    int n;  cin >> n;
    vector<int> ar(n);
    for(int i = 0; i < n; ++i)
      cin >> ar[i];
    printTwoOddOccurring(ar);
    cout << endl;
  }
  return 0;
}

Problem Link
Good Explanation