Skip to content

3215. Count Triplets with Even XOR Set Bits II 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  // Same as 3199. Count Triplets with Even XOR Set Bits I
  long long tripletCount(vector<int>& a, vector<int>& b, vector<int>& c) {
    const auto [evenA, oddA] = getEvenOddBitCount(a);
    const auto [evenB, oddB] = getEvenOddBitCount(b);
    const auto [evenC, oddC] = getEvenOddBitCount(c);
    return static_cast<long>(evenA) * oddB * oddC +
           static_cast<long>(oddA) * evenB * oddC +
           static_cast<long>(oddA) * oddB * evenC +
           static_cast<long>(evenA) * evenB * evenC;
  }

 private:
  // Returns the count of numbers in the `nums` arrays that have even number of
  // ones and odd number of ones in their binary representation.
  pair<int, int> getEvenOddBitCount(const vector<int>& nums) {
    int even = 0;
    int odd = 0;
    for (const unsigned num : nums)
      if (popcount(num) % 2 == 0)
        ++even;
      else
        ++odd;
    return {even, odd};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  // Same as 3199. Count Triplets with Even XOR Set Bits I
  public long tripletCount(int[] a, int[] b, int[] c) {
    final int[] evenOddA = getEvenOddBitCount(a);
    final int[] evenOddB = getEvenOddBitCount(b);
    final int[] evenOddC = getEvenOddBitCount(c);
    final int evenA = evenOddA[0];
    final int evenB = evenOddB[0];
    final int evenC = evenOddC[0];
    final int oddA = evenOddA[1];
    final int oddB = evenOddB[1];
    final int oddC = evenOddC[1];
    return (long) evenA * oddB * oddC + (long) oddA * evenB * oddC + (long) oddA * oddB * evenC +
        (long) evenA * evenB * evenC;
  }

  // Returns the count of numbers in the `nums` arrays that have even number of
  // ones and odd number of ones in their binary representation.
  private int[] getEvenOddBitCount(int[] nums) {
    int even = 0;
    int odd = 0;
    for (final int num : nums)
      if (Integer.bitCount(num) % 2 == 0)
        ++even;
      else
        ++odd;
    return new int[] {even, odd};
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  # Same as 3199. Count Triplets with Even XOR Set Bits I
  def tripletCount(self, a: list[int], b: list[int], c: list[int]) -> int:
    evenA, oddA = self._getEvenOddBitCount(a)
    evenB, oddB = self._getEvenOddBitCount(b)
    evenC, oddC = self._getEvenOddBitCount(c)
    return evenA * oddB * oddC + oddA * evenB * oddC + oddA * oddB * evenC + evenA * evenB * evenC

  def _getEvenOddBitCount(self, nums: list[int]) -> tuple[int, int]:
    """
    Returns the count of numbers in the `nums` arrays that have even number of
    ones and odd number of ones in their binary representation.
    """
    even = sum(num.bit_count() % 2 == 0 for num in nums)
    return (even, len(nums) - even)