04. Find element occurring once when all others are present thrice

The problem can be found at the following link: Question Link

My Approach

The idea is to use a bitwise counting algorithm.

• We maintain an array bits of size 32 to store the count of set bits at each position for all the numbers in the array.

• Then, we iterate through the array and update the bits array by counting the set bits for each number.

• Finally, we go through the bits array and construct the result by adding the bits where the count is not a multiple of 3.

Time and Auxiliary Space Complexity

• Time Complexity: O(N), where N is the length of the input array.

• Auxiliary Space Complexity: O(1) (as we use only a constant 32 size vector).

Code (C++)

class Solution {
  public:
    int singleElement(int arr[], int N) {
        vector<int> bits(32, 0);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 32; j++) {
                bits[j] += arr[i] & 1;
                arr[i] >>= 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < 32; i++)
            if (bits[i] % 3 != 0)
                ans += 1 << i;

        return ans;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.