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 I

Number: 3506

Difficulty: Easy

Paid? Yes

Companies: Amazon

Problem Description

Given three integer arrays a, b, and c, count how many triplets (a[i], b[j], c[k]) result in a XOR value (a[i] XOR b[j] XOR c[k]) that has an even number of set bits.

Key Insights

  • The XOR operation is associative and commutative; however, since we need to count set bits, we compute the XOR for each combination.
  • For each triplet, count the number of set bits in the XOR result.
  • A naive solution, iterating through every possible triplet, is feasible given the constraint (max 100 elements per array).

Space and Time Complexity

Time Complexity: O(n_a * n_b * n_c) where n_a, n_b, n_c are the lengths of arrays a, b, and c respectively. Space Complexity: O(1) extra space (excluding the input arrays).

Solution

We iterate through every possible triplet using three nested loops. For each triplet, compute the XOR of the three numbers. Then, count the number of set bits (using a helper function or built-in functionality in some languages). If the count is even, increment our result counter. Since each array has a maximum length of 100, this straightforward approach is efficient enough. The main trick is correctly counting the set bits in the XORed result.

Code Solutions

# Python solution with line-by-line comments

def count_set_bits(n):
    # Count the number of set bits in the integer n using bin() function.
    return bin(n).count("1")

def count_triplets(a, b, c):
    # Initialize counter for valid triplets.
    count = 0
    # Iterate over every element in array a.
    for i in a:
        # Iterate over every element in array b.
        for j in b:
            # Iterate over every element in array c.
            for k in c:
                # Compute XOR of the three elements.
                xor_value = i ^ j ^ k
                # Check if the number of set bits in xor_value is even.
                if count_set_bits(xor_value) % 2 == 0:
                    # Increment count if condition met.
                    count += 1
    # Return the total count of valid triplets.
    return count

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