Two Numbers With Odd Occurrences

I really like coding here, its such a well made online coding editor and judge. I miss practicing here. Does anyone has an archive of old A2Z sheet page (with all codingStudio links) Would be great!!

import java.util.HashMap;

public class Solution {

    public static int[] twoOddNum(int[] arr) {

        // Using HashMap to count occurrences of each number

        HashMap<Integer, Integer> h = new HashMap<>();

        for (int num : arr) {

            h.put(num, h.getOrDefault(num, 0) + 1);

        }

        int[] result = new int[2];

        int index = 0;

        // Iterate through the HashMap entries to find the two numbers with odd occurrences

        for (HashMap.Entry<Integer, Integer> entry : h.entrySet()) {

            if (entry.getValue() % 2 != 0) {

                result[index++] = entry.getKey();

                if (index == 2) {

                    break; // Found both odd numbers, no need to continue

                }

            }

        }

        // Sort the result array in descending order

        if (result[0] < result[1]) {

            int temp = result[0];

            result[0] = result[1];

            result[1] = temp;

        }

        return result;

    }

}

vector<int> twoOddNum(vector<int> arr)

{

    int XORR= 0;

    int n = arr.size();

    for (int i = 0; i < n; i++)

    {

        XORR^=arr[i];

    }

    int Rightmost = XORR & (~(XORR - 1));

    int b1 = 0;

    int b2 = 0;

    for (int i = 0; i < n; i++)

    {

        if (arr[i] & Rightmost)

        {

            b1^=arr[i];

        }

        else

        {

            b2^=arr[i];

        }

    }

    if (b1 < b2) return {b2,b1};

    else return {b1,b2};

}

vector<int> twoOddNum(vector<int> arr){

    vector<int> ans;

    unordered_map<int,int> mp;

    int N=arr.size();

    for(int i=0;i<N;i++){

        mp[arr[i]]++;

    }

    for(auto x:mp){

        if(x.second%2==1){

            ans.push_back(x.first);

        }

    }

     if (ans[0] < ans[1])

    {

        swap(ans[0], ans[1]);

    }

    return ans;

}

vector<int> twoOddNum(vector<int> arr){
    int num = 0;
    vector<int> ans;

    for(auto it : arr){
        num = num^it;
    }

    int temp = 1;

    while(temp <= num){
        if((temp&num) != 0) break;
        temp = temp << 1;
    }

    int setBit = 0;
    int unsetBit = 0;

    for(auto it : arr){
        if((it&temp) == 0) unsetBit = unsetBit^it;
        else setBit = setBit^it;
    }

    if(setBit > unsetBit){
        ans.push_back(setBit);
        ans.push_back(unsetBit);
    }
    else{
        ans.push_back(unsetBit);
        ans.push_back(setBit);
    }

    return ans;
}

Initialize XOR variable (xr) to 0:

• int xr = 0;
• This variable will be used to store the XOR of all elements in the array. We start with 0 because XOR of any number with 0 is the number itself.

Calculate XOR of all elements in the array:

• for(auto i : arr) { xr ^= i; }
• This loop iterates through each element i in the array arr.
• It calculates the XOR of each element with the current value of xr.
• After this loop, xr will contain the XOR of all elements in the array.

Find the rightmost set bit in xr:

• int dn = xr & (xr - 1) ^ xr;
• This line calculates the rightmost set bit in xr.
• (xr - 1) flips all the bits to the right of the rightmost set bit in xr.
• xr & (xr - 1) removes the rightmost set bit from xr.
• ^ xr then adds back the rightmost set bit. So dn will contain only the rightmost set bit of xr.

Initialize variables to store the two odd occurring numbers:

• int xr1 = 0, xr2 = 0;
• xr1 and xr2 will be used to store the two numbers that occur an odd number of times.

Iterate through the array again to separate numbers based on the rightmost set bit:

Explanation:

• This loop iterates through each element i in the array arr.
• It checks if the rightmost set bit of xr is set in the current element i by performing dn & i.
• If the rightmost set bit is set, it XORs i with xr1, otherwise with xr2.
• This effectively separates the numbers into two groups based on the rightmost set bit.

Return the two odd occurring numbers:

Explanation:

• It checks if xr1 is greater than xr2.
• If so, it returns {xr1, xr2}, otherwise {xr2, xr1}.
• The order of the numbers returned is not guaranteed, but this ensures they are returned in ascending order.

Time Complexity:

• The loop that calculates xr iterates through the array once, so it has a time complexity of O(n).
• The second loop also iterates through the array once, so it also has a time complexity of O(n).
• Overall, the time complexity of the algorithm is O(n).

Space Complexity:

The algorithm uses a constant amount of extra space regardless of the size of the input array, so the space complexity is O(1).

CODE:

vector<int> twoOddNum(vector<int> arr){

    // Write your code here.

    int xr=0;

    for(auto i:arr){

        xr^=i;

    }

    int dn=xr&(xr-1)^xr;

    int xr1=0,xr2=0;

    for(auto i:arr){

        if(dn&i)xr1^=i;

        else xr2^=i;

    }

    if(xr1>xr2)return {xr1,xr2};

    return {xr2,xr1};

}

Eg. 1^3^3^3^2^2^4^4 (Here 1 comes 1 time and 3 comes 3 times)

XOR = 1 ^ 3 (As remaining is 0);

XOR = 2 => 10 means that 1 & 3 differ at

1st bit with one number (here its 3) having it as set while the other (1 in this case) has it as unset.

Now we need to find the first bit from right that is different for both numbers.

Which simply means to get the first set bit of XOR. and we get that from

(xor & (xor-1)) ^ xor;

-> xor & (xor-1) -> this unsets the rightmost set bit , then ^XOR gets backs only the rightmost set bit.

-> (2 & (2-1)) = 10 & 01 = 00 (Rightmost set bit unset)

-> (2 & (2-1)) ^ 2 => 00 ^ 10 = 10 (gets only the rightmost set bit)

Now iterate through each number and check if it has a set bit at the rightmost set bit.

If yes then put 1 bucket :=> 3 ^ 3 ^ 3 ^ 2 ^2 = 3

If No then put in another bucket :=> 1 ^ 4 ^ 4 = 1

Bucket means variable and keep xorring into it. At the end both buckets will have the odd occured

numbers each.

public static int[] twoOddNum(int []arr){
        int xor = 0;
        for(int n: arr) xor ^= n;
        xor = (xor & (xor-1)) ^ xor; 
        int setBucket = 0;
        int unsetBucket = 0;
        for(int n: arr) {
            if((xor & n) == 0) {
                unsetBucket ^= n;
            }
            else {
                setBucket ^= n;
            }
        }

        int[] op = {setBucket, unsetBucket};

        if(op[0] < op[1]) {
            int temp = op[0];
            op[0] = op[1];
            op[1] = temp;
        }

        return op;
    }

#include <vector>
#include <algorithm>

std::vector<int> twoOddNum(std::vector<int> arr) {
    std::sort(arr.begin(), arr.end()); // Sort the array first

    std::vector<int> result;

    int count = 1;
    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] == arr[i - 1]) {
            count++;
        } else {
            if (count % 2 != 0) {
                result.push_back(arr[i - 1]);
            }
            count = 1;
        }
    }

    // Handle the last element
    if (count % 2 != 0) {
        result.push_back(arr.back());
    }

    // Remove duplicates
    result.erase(std::unique(result.begin(), result.end()), result.end());

    // Sort in descending order
    std::sort(result.begin(), result.end(), std::greater<int>());

    return result;
}

vector<int> twoOddNum(vector<int> arr) {
  int n = arr.size(), res = 0, ind = 0, x1 = 0, x2 = 0;

  // count the resultant XOR of all arr elems
  for (int i = 0; i < n; i++)
    res ^= arr[i];

  // find the position of last set bit
  while (res) {
    if (res & 1)
      break;
    ind++;
    res >>= 1;
  }
  // now left shifting 1 ind times to get the 2^ind
  ind = 1 << ind;

  // we are segrigating all the set bits in x1 and non set bits to x2
  // as XOR is diff in bits between numbers
  // we have to get two digit such that by XORing that two number 
  // we get the res which we calculated before
  for (int i = 0; i < n; i++) {
    if (arr[i] & ind)
      x1 ^= arr[i];
    else
      x2 ^= arr[i];
  }

  // To return them in decreasing order
  if (x1 < x2)
    swap(x1, x2);

  return {x1, x2};
}

vector<int> twoOddNum(vector<int> arr){
    // Write your code here.
    int XOR = 0;
    
    // Find XOR of all elements in the array
    for (int num : arr) {
        XOR ^= num;
    }

    // Find the rightmost set bit in XOR
    int rightmostSetBit = XOR & -XOR;

    // Initialize two numbers with odd occurrences
    int num1 = 0, num2 = 0;

    // Partition the array based on the rightmost set bit
    for (int num : arr) {
        if (num & rightmostSetBit) {
            // Group 1 (rightmost set bit is set)
            num1 ^= num;
        } else {
            // Group 2 (rightmost set bit is not set)
            num2 ^= num;
        }
    }

    // Ensure num1 is greater than num2
    if (num1 < num2) {
        swap(num1, num2);
    }

    return {num1, num2};
}