Welcome to Subscribe On Youtube

3199. Count Triplets with Even XOR Set Bits I 🔒

Description

Given three integer arrays a, b, and c, return the number of triplets (a[i], b[j], c[k]), such that the bitwise XOR of the elements of each triplet has an even number of set bits.

 

Example 1:

Input: a = [1], b = [2], c = [3]

Output: 1

Explanation:

The only triplet is (a[0], b[0], c[0]) and their XOR is: 1 XOR 2 XOR 3 = 002.

Example 2:

Input: a = [1,1], b = [2,3], c = [1,5]

Output: 4

Explanation:

Consider these four triplets:

• (a[0], b[1], c[0]): 1 XOR 3 XOR 1 = 0112
• (a[1], b[1], c[0]): 1 XOR 3 XOR 1 = 0112
• (a[0], b[0], c[1]): 1 XOR 2 XOR 5 = 1102
• (a[1], b[0], c[1]): 1 XOR 2 XOR 5 = 1102

 

Constraints:

• 1 <= a.length, b.length, c.length <= 100
• 0 <= a[i], b[i], c[i] <= 100

Solutions

Solution 1: Bit Manipulation

For two integers, the parity of the number of $1$s in the XOR result depends on the parity of the number of $1$s in the binary representations of the two integers.

We can use three arrays cnt1, cnt2, cnt3 to record the parity of the number of $1$s in the binary representations of each number in arrays a, b, c, respectively.

Then, we enumerate the parity of the number of $1$s in the binary representations of each number in the three arrays within the range $[0, 1]$. If the sum of the parity of the number of $1$s in the binary representations of three numbers is even, then the number of $1$s in the XOR result of these three numbers is also even. At this time, we multiply the combination of these three numbers and accumulate it into the answer.

Finally, return the answer.

The time complexity is $O(n)$, where $n$ is the length of arrays a, b, c. The space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int tripletCount(int[] a, int[] b, int[] c) {
          int[] cnt1 = new int[2];
          int[] cnt2 = new int[2];
          int[] cnt3 = new int[2];
          for (int x : a) {
              ++cnt1[Integer.bitCount(x) & 1];
          }
          for (int x : b) {
              ++cnt2[Integer.bitCount(x) & 1];
          }
          for (int x : c) {
              ++cnt3[Integer.bitCount(x) & 1];
          }
          int ans = 0;
          for (int i = 0; i < 2; ++i) {
              for (int j = 0; j < 2; ++j) {
                  for (int k = 0; k < 2; ++k) {
                      if ((i + j + k) % 2 == 0) {
                          ans += cnt1[i] * cnt2[j] * cnt3[k];
                      }
                  }
              }
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int tripletCount(vector<int>& a, vector<int>& b, vector<int>& c) {
          int cnt1[2]{};
          int cnt2[2]{};
          int cnt3[2]{};
          for (int x : a) {
              ++cnt1[__builtin_popcount(x) & 1];
          }
          for (int x : b) {
              ++cnt2[__builtin_popcount(x) & 1];
          }
          for (int x : c) {
              ++cnt3[__builtin_popcount(x) & 1];
          }
          int ans = 0;
          for (int i = 0; i < 2; ++i) {
              for (int j = 0; j < 2; ++j) {
                  for (int k = 0; k < 2; ++k) {
                      if ((i + j + k) % 2 == 0) {
                          ans += cnt1[i] * cnt2[j] * cnt3[k];
                      }
                  }
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def tripletCount(self, a: List[int], b: List[int], c: List[int]) -> int:
          cnt1 = Counter(x.bit_count() & 1 for x in a)
          cnt2 = Counter(x.bit_count() & 1 for x in b)
          cnt3 = Counter(x.bit_count() & 1 for x in c)
          ans = 0
          for i in range(2):
              for j in range(2):
                  for k in range(2):
                      if (i + j + k) & 1 ^ 1:
                          ans += cnt1[i] * cnt2[j] * cnt3[k]
          return ans
  
  

• func tripletCount(a []int, b []int, c []int) (ans int) {
  	cnt1 := [2]int{}
  	cnt2 := [2]int{}
  	cnt3 := [2]int{}
  	for _, x := range a {
  		cnt1[bits.OnesCount(uint(x))%2]++
  	}
  	for _, x := range b {
  		cnt2[bits.OnesCount(uint(x))%2]++
  	}
  	for _, x := range c {
  		cnt3[bits.OnesCount(uint(x))%2]++
  	}
  	for i := 0; i < 2; i++ {
  		for j := 0; j < 2; j++ {
  			for k := 0; k < 2; k++ {
  				if (i+j+k)%2 == 0 {
  					ans += cnt1[i] * cnt2[j] * cnt3[k]
  				}
  			}
  		}
  	}
  	return
  }
  

• function tripletCount(a: number[], b: number[], c: number[]): number {
      const cnt1: [number, number] = [0, 0];
      const cnt2: [number, number] = [0, 0];
      const cnt3: [number, number] = [0, 0];
      for (const x of a) {
          ++cnt1[bitCount(x) & 1];
      }
      for (const x of b) {
          ++cnt2[bitCount(x) & 1];
      }
      for (const x of c) {
          ++cnt3[bitCount(x) & 1];
      }
      let ans = 0;
      for (let i = 0; i < 2; ++i) {
          for (let j = 0; j < 2; ++j) {
              for (let k = 0; k < 2; ++k) {
                  if ((i + j + k) % 2 === 0) {
                      ans += cnt1[i] * cnt2[j] * cnt3[k];
                  }
              }
          }
      }
      return ans;
  }
  
  function bitCount(i: number): number {
      i = i - ((i >>> 1) & 0x55555555);
      i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
      i = (i + (i >>> 4)) & 0x0f0f0f0f;
      i = i + (i >>> 8);
      i = i + (i >>> 16);
      return i & 0x3f;
  }
  
  

All Problems

All Solutions