We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Triplets with Even XOR Set Bits II

Number: 3521

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given three integer arrays a, b, and c, count the number of triplets (a[i], b[j], c[k]) such that the XOR of the three numbers has an even number of set bits. In other words, compute the number of triplets where the parity (even/odd) of the total count of ones in the binary representation of (a[i] XOR b[j] XOR c[k]) is even.

Key Insights

  • The parity (even or odd) of the number of set bits in a number is equivalent to the number modulo 2 of set bits.
  • XOR’s effect on bit parity can be seen as a sum modulo 2. Thus, the parity of (a XOR b XOR c) is the XOR of the parities of a, b, and c.
  • A triplet (x, y, z) will have an even overall parity if either all three numbers have even parity or exactly one number is even and the other two are odd.
  • Count the numbers with even and odd set bits in each array, then compute the total triplets by multiplying appropriate counts.

Space and Time Complexity

Time Complexity: O(nA + nB + nC) where nA, nB, and nC are the lengths of arrays a, b, and c respectively. Space Complexity: O(1)

Solution

The solution involves the following steps:

  1. Define a helper function to count the number of elements with even and odd set bits in an array.
  2. For each array (a, b, and c), compute the count of numbers with an even number of set bits (even count) and with an odd number of set bits (odd count).
  3. Recognize that the XOR of three numbers yields even parity in two cases:
    • All three numbers are even.
    • One number is even and the other two are odd.
  4. Compute the result as: (even count from a * even count from b * even count from c) + (even count from a * odd count from b * odd count from c) + (odd count from a * even count from b * odd count from c) + (odd count from a * odd count from b * even count from c).
  5. Return the computed result.

Code Solutions

def countTriplets(a, b, c):
    # Helper function to count even and odd parity numbers
    def count_even_odd(arr):
        even = odd = 0
        for num in arr:
            # Count the number of set bits and determine parity
            if bin(num).count("1") % 2 == 0:
                even += 1
            else:
                odd += 1
        return even, odd

    a_even, a_odd = count_even_odd(a)
    b_even, b_odd = count_even_odd(b)
    c_even, c_odd = count_even_odd(c)

    # Calculate the result using the parity conditions:
    # 1. (even, even, even)
    # 2. (even, odd, odd)
    # 3. (odd, even, odd)
    # 4. (odd, odd, even)
    result = (a_even * b_even * c_even +
              a_even * b_odd  * c_odd  +
              a_odd  * b_even * c_odd  +
              a_odd  * b_odd  * c_even)
    return result

# Example usage:
a = [1, 1]
b = [2, 3]
c = [1, 5]
print(countTriplets(a, b, c))  # Expected output: 4
← Back to All Questions